樹狀數(shù)組維護區(qū)間和的模型及其拓廣的簡單總結(jié)by wyl8899 樹狀數(shù)組的基本知識已經(jīng)被講到爛了，我就不多說了，下面直接給出基本操作的代碼。假定原數(shù)組為a1.n，樹狀數(shù)組b1.n，考慮靈活性的需要，代碼使用int *a傳數(shù)組。#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)返回原數(shù)組1,x的區(qū)間和，update(x,w)將原數(shù)組下標為x的數(shù)加上w。這兩個函數(shù)使用O(操作數(shù)*logn)的時間和O(n)的空間完成單點加減，區(qū)間求和的功能。 接下來做一些升級，讓樹狀數(shù)組完成區(qū)間加減，單點查詢的功能。直接做的話很困難，需要對問題做一些轉(zhuǎn)化。考慮將原數(shù)組差分，即令di=ai-ai-1，特別地，d1=a1。此時ai=d1+.+di，所以單點查詢ai實際上就是在求d數(shù)組的1.i區(qū)間和。而區(qū)間l,r整體加上k的操作，可以簡單地使用dl+=k和dr+1-=k來完成。于是，我們用樹狀數(shù)組來維護d，就可以解決問題了。 下面再升級一次，完成區(qū)間加減，區(qū)間求和的功能。仍然沿用d數(shù)組，考慮a數(shù)組1,x區(qū)間和的計算。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)所以我們再用樹狀數(shù)組維護一個數(shù)組d2i=di*i，即可完成任務(wù)。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的時候，我們就只維護后來加上去的部分，查詢區(qū)間和的時候再補上初始的時候這一段的區(qū)間和就可以了。=一維到二維的分割線=接下來到二維樹狀數(shù)組。先看看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，由于需要多次調(diào)用的緣故，改成了更短的名字。單點加減，矩形求和并不難，直接用上面的兩段就行了。需要注意的是矩形的求和怎么求。上面的代碼返回的是(1,1)-(x,y)矩形的和。那么(x1,y1)-(x2,y2)的矩形和由下式給出：sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)畫個圖就很好理解了。對于涉及矩形加減的情形，我們發(fā)現(xiàn)一維中的差分的辦法在二維的情況用不出來，所以要改一下。思考一下一維中的差分的另外一個含義：di同時也表示di.n的整體增量，di+=k就意味著把di.dn全部加上了k。理解了之后就發(fā)現(xiàn)這個意義上可以推廣到二維，仍假設(shè)原矩形初始全為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)的和，結(jié)果由下式給出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一共四個二維樹狀數(shù)組，問題得到解決。tyvj p1716就是實現(xiàn)這兩個功能的裸題，下面給出完整代碼。 / 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