差分详解+树状数组扩展
程序员文章站
2022-06-01 11:52:53
...
前言:现在还不是很懂,不过先把模板抄在这里把。
介绍一下差分,一个很简单的东西。
一、简介
已知数组a为1,2,1,5,7,4
那么差分数组1,1,-1,4,2,-3
显然,差分数组就是当前项与前一项的差值。
容易得到,an就是差分数组的前n项和。
二、那么有什么便利的地方呢?
我们假想一下,现在要给1至4的区间每个数加上1,那么差分数组会变成什么样呢,模拟一下得
a数组2,3,2,6,8,5
差分数组2,1,-1,4,1,-3
可以看到,只有下标为1和5的地方发生了变化。
刚才我们说到,差分数组的前n项和就是an,那我们在差分数组的1处加1,在5处减1,那么1到4利用差分数组前缀和求an,an的值确实都加了1,当我们求a5以后的数的话,我们就不需要加1了,所以差分数组a5处减1.
这样,差分数组的前缀和仍然是an。
树状数组+差分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,tree[500009];
ll lowbit(ll x){
return x&(-x);
}
ll sumn(ll x){
ll ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void add(ll x,ll w){
while(x<=n){
tree[x]+=w;
x+=lowbit(x);
}
}
int main()
{
cin>>n>>m;
ll last=0,nows=0;
for(int i=1;i<=n;i++)
{
scanf("%ld",&nows);
add(i,nows-last);
last=nows;
}
for(int i=1;i<=m;i++)
{
ll mid,l,r,q;
cin>>mid;
if(mid==1)
{
cin>>l>>r>>q;
add(l,q);
add(r+1,-q);
}
else
{
cin>>l;
cout<<sumn(l)<<endl;
}
}
}
上一篇: 用指针数组实现的矩阵类
下一篇: 模板标签调用说明
推荐阅读
-
ES6数组的扩展详解
-
树状数组:单点修改,区间查询(详解)
-
【做练习】最大上升子序列(树状数组) 树状数组的原理及应用详解
-
Python计算双重差分模型DID及其对应P值使用详解
-
2020秦皇岛CCPC 7-2 Bounding Wall(树状数组+二分,并查集)
-
BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)
-
PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解
-
洛谷P3246 [HNOI2016]序列(离线 差分 树状数组)
-
Tunnel Warfare(树状数组+二分)
-
【数字_ID】HDU6274 Master of Sequence(二分+树状数组+预处理)