如何利用树状数组修改一个区间?

发布网友发布时间：2022-04-24 20:53

共4个回答

热心网友时间：2022-04-12 20:20

给你一个树状数组区间修改区间查询的模板吧

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];
}
*/

热心网友时间：2022-04-12 21:38

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/38413895。

热心网友时间：2022-04-12 23:12

向上求和，向下修改。
具体的不清楚。