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

树状数组维护区间和的模型及其拓广的简单总结by wyl8899 树状数组的基本知识已经被讲到烂了，我就不多说了，下面直接给出基本操作的代码。假定原数组为a1.n，树状数组b1.n，考虑灵活性的需要，代码使用int *a传数组。#define lowbit(x) (x)&(-(x)int sum(int *a,int x) int s=0; for(;x;x-=lowbit(x)s+=ax; return s;void update(int *a,int x,int w) for(;x=n;x+=lowbit(x)ax+=w;sum(x)返回原数组1,x的区间和，update(x,w)将原数组下标为x的数加上w。这两个函数使用O(操作数*logn)的时间和O(n)的空间完成单点加减，区间求和的功能。 接下来做一些升级，让树状数组完成区间加减，单点查询的功能。直接做的话很困难，需要对问题做一些转化。考虑将原数组差分，即令di=ai-ai-1，特别地，d1=a1。此时ai=d1+.+di，所以单点查询ai实际上就是在求d数组的1.i区间和。而区间l,r整体加上k的操作，可以简单地使用dl+=k和dr+1-=k来完成。于是，我们用树状数组来维护d，就可以解决问题了。 下面再升级一次，完成区间加减，区间求和的功能。仍然沿用d数组，考虑a数组1,x区间和的计算。d1被累加了x次，d2被累加了x-1次，.，dx被累加了1次。因此得到sigma(ai)=sigmadi*(x-i+1)=sigma di*(x+1) - di*i =(x+1)*sigma(di)-sigma(di*i)所以我们再用树状数组维护一个数组d2i=di*i，即可完成任务。POJ 3468就是这个功能的裸题，下面给出代码。请注意我们上面的讨论都假定了a初始全是0。如果不是这样呢?下面的程序里给出了一个相对简便的处理办法。/ POJ 3468 Using BIT #include const int maxn=100010;_int64 amaxn,bmaxn,cmaxn;int n,m; inline int lowbit(const int &x) return x&(-x); _int64 query(_int64 *a,int x) _int64 sum=0; while(x)sum+=ax;x-=lowbit(x); return sum; void update(_int64 *a,int x,_int64 w) while(x=n)ax+=w;x+=lowbit(x); int main() int l,r,i; _int64 ans,w; char ch; scanf(%d%d,&n,&m); a0=0; for(i=1;i=n;+i) scanf(%I64d,&ai); ai+=ai-1; while(m-) scanf(%c,&ch); while(ch!=Q & ch!=C)scanf(%c,&ch); if(ch=Q) scanf(%d%d,&l,&r); ans=ar-al-1+(r+1)*query(b,r)-l*query(b,l-1)-query(c,r)+query(c,l-1); printf(%I64dn,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 amaxnmaxn,int x,int y) int s=0,t; for(;x;x-=lowbit(x) for(t=y;t;t-=lowbit(t) s+=axt; return s;inline void gp(int amaxnmaxn,int x,int y,int w) int t; for(;x=n;x+=lowbit(x) for(t=y;t=m;t+=lowbit(t) axt+=w;gs就是sum，gp就是update，由于需要多次调用的缘故，改成了更短的名字。单点加减，矩形求和并不难，直接用上面的两段就行了。需要注意的是矩形的求和怎么求。上面的代码返回的是(1,1)-(x,y)矩形的和。那么(x1,y1)-(x2,y2)的矩形和由下式给出：sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)画个图就很好理解了。对于涉及矩形加减的情形，我们发现一维中的差分的办法在二维的情况用不出来，所以要改一下。思考一下一维中的差分的另外一个含义：di同时也表示di.n的整体增量，di+=k就意味着把di.dn全部加上了k。理解了之后就发现这个意义上可以推广到二维，仍假设原矩形初始全为0，以便接下来的叙述。令ax,y表示(x,y)-(n,m)矩形的整体增量，其中(n,m)是边界。那么(x1,y1)-(x2,y2)矩形整体加k的代码就是gp(a,x1,y1,w); gp(a,x2+1,y1,-w);gp(a,x1,y2+1,-w); gp(a,x2+1,y2+1,w);仍然是建议画个图来帮助理解。至此，矩形加减，单点查询的问题得到了解决。重头戏在这里，矩形加减，矩形求和。求原矩形(1,1)-(x,y)的和，结果由下式给出sigma(i=1.x,j=1.y) ai,j*(x-i+1)*(y-j+1)很好理解吧? 但是这个式子并不是那么容易求和的，展开一下求和的部分得到ai,j* ( (x+1)(y+1) - (x+1)*j - (y+1)*x + i*j )整个式子就是(x+1)(y+1)sigma(ai,j) - (x+1)sigma(ai,j*j) - (y+1)sigma(ai,j*i) + sigma(ai,j*i*j)知道怎么处理了吧？如果没有请回去复习一维的处理方法。令bi,j=ai,j*i ci,j=ai,j*j di,j=ai,j*i*j维护a,b,c,d一共四个二维树状数组，问题得到解决。tyvj p1716就是实现这两个功能的裸题，下面给出完整代码。 / tyvj p1716 using 2D BIT#include#include#define lowbit(x) (x)&(-(x)const int maxn=2049;int amaxnmaxn,bmaxnmaxn,cmaxnmaxn,dmaxnmaxn;int n,m; inline int gs(int amaxnmaxn,int x,int y) int s=0,t; for(;x;x-=lowbit(x) for(t=y;t;t-=lowbit(t) s+=axt; return s; inline void gp(int amaxnmaxn,int x,int y,int w) int t; for(;x=n;x+=lowbit(x) for(t=y;t=m;t+=lowbit(t) axt+=w; inline int sum(int x,int y) return (x+1)*(y+1)*gs(a,x,y)-(y+1)*gs(b,x,y)-(x+1)*gs(c,x,y)+gs(d,x,y); inline void update(int x1,int y1,int x2,int y2,int w) gp(a,x1,y1,w); gp(a,x2+1,y1,-w); gp(a,x1,y2+1,-w); gp(a,x2+1,y2+1,w); gp(b,x1,y1,w*x1); gp(b,x2+1,y1,-w*(x2+1); gp(b,x1,y2+1,-w*x1); gp(b,x2+1,y2+1,w*(x2+1); gp(c,x1,y1,w*y1); gp(c,x2+1,y1,-w*y1); gp(c,x1,y2+1,-w*(y2+1); gp(c,x2+1,y2+1,w*(y2+1); gp(d,x1,y1,w*x1*y1); gp(d,x2+1,y1,-w*(x2+1)*y1); gp(d,x1,y2+1,-w*x1*(y2+1); gp(d,x2+1,y2+1,w*(x2+1)*(y2+1); int main() int x1,y1,x2,y2,w; char ch; scanf(%c,&ch); while(ch!=X)scanf(%c,&ch); scanf(%d%dn,&n,&m); memset(a,0,sizeof(a); memset(b,0,sizeof(b); memset(c,0,sizeof(c); memset(d,0,sizeof(d); while(scanf(%c,&ch)!=EOF) scan