树状数组维护区间与的模型及其拓广的简单总结.doc

树状数组维护区间和的模型及其拓广的简单总结 by wyl8899 树状数组的基本知识已经被讲到烂了，我就不多说了，下面直接给出基本操作的代码。 假定原数组为a[1..n]，树状数组b[1..n]，考虑灵活性的需要，代码使用int *a传数组。 #define lowbit(x) ((x)(-(x))) int sum(int *a,int x){ int s=0; for(;x;x-=lowbit(x))s+=a[x]; return s; } void update(int *a,int x,int w){ for(;x=n;x+=lowbit(x))a[x]+=w; } sum(x)返回原数组[1,x]的区间和，update(x,w)将原数组下标为x的数加上w。 这两个函数使用O(操作数*logn)的时间和O(n)的空间完成单点加减，区间求和的功能。 接下来做一些升级，让树状数组完成区间加减，单点查询的功能。 直接做的话很困难，需要对问题做一些转化。 考虑将原数组差分，即令d[i]=a[i]-a[i-1]，特别地，d[1]=a[1]。 此时a[i]=d[1]+..+d[i]，所以单点查询a[i]实际上就是在求d数组的[1..i]区间和。 而区间[l,r]整体加上k的操作，可以简单地使用d[l]+=k和d[r+1]-=k来完成。 于是，我们用树状数组来维护d[]，就可以解决问题了。 下面再升级一次，完成区间加减，区间求和的功能。 仍然沿用d数组，考虑a数组[1,x]区间和的计算。d[1]被累加了x次，d[2]被累加了x-1次，...，d[x]被累加了1次。 因此得到 sigma(a[i]) =sigma{d[i]*(x-i+1)} =sigma{ d[i]*(x+1) - d[i]*i } =(x+1)*sigma(d[i])-sigma(d[i]*i) 所以我们再用树状数组维护一个数组d2[i]=d[i]*i，即可完成任务。 POJ 3468就是这个功能的裸题，下面给出代码。 [请注意我们上面的讨论都假定了a[]初始全是0。如果不是这样呢?下面的程序里给出了一个相对简便的处理办法。] // POJ 3468 Using BIT #include cstdio const int maxn=100010; __int64 a[maxn],b[maxn],c[maxn]; int n,m; inline int lowbit(const int x){ return x(-x); } __int64 query(__int64 *a,int x){ __int64 sum=0; while(x){sum+=a[x];x-=lowbit(x);} return sum; } void update(__int64 *a,int x,__int64 w){ while(x=n){a[x]+=w;x+=lowbit(x);} } int main(){ int l,r,i; __int64 ans,w; char ch; scanf(%d%d,n,m); a[0]=0; for(i=1;i=n;++i){ scanf(%I64d,a[i]); a[i]+=a[i-1]; } while(m--){ scanf(%c,ch); while(ch!=Q ch!=C)scanf(%c,ch); if(ch==Q){ scanf(%d%d,l,r); ans=a[r]-a[l-1]+(r+1)*query(b,r)-l*query(b,l-1)-query(c,r)+query(c,l-1); printf(%I64d\n,ans); }else{ scanf(%d%d%I64d,l,r,w); update(b,l,w); update(b,r+1,-w); update(c,l,w*l); update(c,r+1,-(r+1)*w); } } return 0; } [当a[]初始不全0的时候，我们就只维护后来加上去的部分，查询区间和的时候再补上初始的时候这一段的区间和就可以了。] ======================一维到二维的分割线========================= 接下来到二维树状数组。 先看看sum和update变成什么样子了吧。 inline int gs(int a[maxn][ma