树状数组万能讲义.doc

数据结构树状数组专题做数据结构的题真是异常的能让人感到自己在脱菜的路上迈进啊。这一次来看看树状数组。树状数组的基本知识已经被各种大牛和菜鸟讲到烂了，我就不多说了，下面给出基本操作的代码。假定原数组为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。那么区间l,r整体加上k的操作就可以简单地使用dl+=k;dr+1-=k来完成了。此时ai=d1+.+di，所以单点查询ai实际上就是在求d数组的1.i区间和，很容易完成了。下面再升级一次，完成区间加减，区间求和的功能。仍然沿用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就是这个功能的裸题.下面给出代码：/ POJ 3468 Using BIT#include const int fin=0,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; if(fin) freopen(t.in,r,stdin); freopen(t.out,w,stdout); 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); if(fin) fclose(stdin); fclose(stdout); return 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(y1,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 fin=0,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; if(fin) freopen(t.in,r,stdin); freopen(t.out,w,stdout); 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) scanf(%d%