如何利用树状数组修改一个区间?
发布网友
共4个回答
热心网友
给你一个树状数组区间修改区间查询的模板吧
const int MAXN=5e5+1;int n,a[MAXN];
LL C[2][MAXN];
int mul;
#define lowbit(x) (x&-x)
inline void suf(int x,int d){
mul=x-1;
while(x<=n){
C[0][x]+=d,C[1][x]+=mul*d;
x+=lowbit(x);
}
}
#define update(x,y,d) suf(x,d),suf(y+1,-d)
int ret;
inline int pre(int x){
ret=a[mul=x];
while(x){
ret+=mul*C[0][x]-C[1][x];
x-=lowbit(x);
}
return ret;
}
#define query(x,y) pre(y)-pre(x-1)
/*
a[]预处理
for(int i=1;i<=n;++i){
cin>>a[i];
a[i]+=a[i-1];
}
*/
热心网友
int ADD_B(int x, int v){
for (int i=x; i>0; i-=i&(-i)) B[i]+= v;
return 0;
}
int SUM_B(int x){
int ans = 0;
for (int i=x; i<=n; i+=i&(-i)) s += B[i];
return ans;
}
修改区间[l,r] 加上v，ADD_B(r,v);if (l>1) ADD_B(l-1,v);
查找点x，SUM_B(x);
还可以修改区间查区间，http://blog.csdn.net/lhy1994/article/details/384135。
热心网友
向上求和，向下修改。
具体的不清楚。
