维护差分数组的的树状数组模板题
普通的差分数组只能处理:
1.给某一个位置的值加上一个值
2.查询某一个区间的和
本题的差分数组要处理的问题是
1.给某一个区间的数都统一加上一个值
2.查询某一个位置的值
那么问题可以转化为
差分数组模板题可以参考 AcWing 797. 差分
让树状数组原本维护的是a[]数组的前缀和,改D’x’c成维护数组a[]的差分数组b[]的前缀和
差分数组b[]的前缀和就对应a[]数组
那么例如给$a[]$数组的$[l,r]$区间加上一个值,就可以给差分数组执行$b[l] += c , b[r + 1] -= c$,
那么对应的add操作就是$add(l,c), add(r + 1,-c)$
如果是查询$a[]$数组一个位置$z$的值,那么只需要统计$[1 ~ z]$这一段数组b的前缀和的值即可
维护差分数组的树状数组
c++代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
LL tr[N]; //树状数组
int n,m;
int lowbit(int x){ //获取x的二进制数的最后一个1
return x & -x;
}
void add(int x,int c){ //给第x个数加上c值
for(int i = x;i <= n;i += lowbit(i)){
tr[i] += c;
}
}
LL sum(int x){ //统计1 ~ x的数
LL res = 0;
for(int i = x; i >= 1;i -= lowbit(i)){
res += tr[i];
}
return res;
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
//数状数组里面记录的是a[]数组的差分数组
for(int i = 1;i <= n;++i){
//给第i个数加上a[i] - a[i - 1]
add(i,a[i]- a[i - 1]);
}
while(m--){
char op[2];
int l,r,d;
scanf("%s%d",op,&l);
if(op[0] == 'C'){
cin >> r >> d;
//给[l,r]加上d值,相当于差分数组b[l] += c , b[r + 1] -= c
add(l,d);
add(r + 1,-d);
}else{
//查询第l个数,相当于统计b[0],b[1],.... b[x]的前缀和
LL res = sum(l);
cout << res << endl;
}
}
return 0;
}