樹狀數(shù)組萬(wàn)能講義

1、數(shù)據(jù)結(jié)構(gòu) 樹狀數(shù)組專題做數(shù)據(jù)結(jié)構(gòu)的題真是異常的能讓人感到自己在脫菜的路上邁進(jìn)啊。這一次來(lái)看看樹狀數(shù)組。樹狀數(shù)組的基本知識(shí)已經(jīng)被各種大牛和菜鳥講到爛了，我就不多說(shuō)了， 下面給出基本操作的代碼。假定原數(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; s

2、um(x) 返回原數(shù)組 1,x 的區(qū)間和， update(x,w)將原數(shù)組下標(biāo)為x 的數(shù)加上w 。這兩個(gè)函數(shù)使用o(logn) 的時(shí)間和o(n) 的空間完成單點(diǎn)加減，區(qū)間求和的功能。接下來(lái)做一些升級(jí)，讓樹狀數(shù)組完成區(qū)間加減，單點(diǎn)查詢的功能。考慮將原數(shù)組差分，令di=ai-ai-1，特別地， d1=a1。那么區(qū)間 l,r 整體加上 k 的操作就可以簡(jiǎn)單地使用dl+=k;dr+1-=k來(lái)完成了。此時(shí) ai=d1+.+di，所以單點(diǎn)查詢ai 實(shí)際上就是在求d 數(shù)組的 1.i 區(qū)間和， 很容易完成了。下面再升級(jí)一次，完成區(qū)間加減，區(qū)間求和的功能。仍然沿用d 數(shù)組，考慮a 數(shù)組1,x 區(qū)間和的計(jì)算。d1

3、 被累加了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) 所以我們?cè)儆脴錉顢?shù)組維護(hù)一個(gè)數(shù)組d2i=di*i，即可完成任務(wù)。poj 3468就是這個(gè)功能的裸題.下面給出代碼：/ poj 3468 using bit #include const int fin=0,maxn=100010; _int64 amaxn,bmaxn,cmaxn; int n,m; inline int lowbit(const int &

4、;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,&

5、;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);

6、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; =一維到二維的分割線= 接下來(lái)到二維樹狀數(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(i

7、nt 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ǎn)加減，矩形求和并不難，直接套用上面的兩段就行了。需要注意的是矩形的求和怎么求。上面的代碼返回的是(1,1)-(x,y) 矩形的和。那么 (x1,y1)-(x2,y2)的矩形和由下式給出：sum(y1,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1) 畫個(gè)圖就很好理解了。矩形加減，單點(diǎn)查詢

8、也不難，套用一維的推廣方式就可以了，這里略去。重頭戲在這里，矩形加減，矩形求和。一維中的差分的辦法在二維的情況用不出來(lái)，所以要改一下。思考一下一維中的差分的另外一個(gè)含義：di 同時(shí)也表示di.n 的整體增量，di+=k就意味著把 di.dn全部加上了k。理解了之后就發(fā)現(xiàn)這個(gè)意義上可以推廣到二維，假設(shè)原矩形初始全為0， 以便接下來(lái)的敘述。令 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,

9、y2+1,w); 老樣子，畫個(gè)圖就可以理解了。接下來(lái)就是求和。求原矩形(1,1)-(x,y) 的和，結(jié)果由下式給出sigma(i=1.x,j=1.y) ai,j*(x-i+1)*(y-j+1) 很好理解吧 ? 但是這個(gè)式子并不是那么容易求和的，展開一下求和的部分得到ai,j* ( (x+1)(y+1) - (x+1)*j - (y+1)*x + i*j ) 整個(gè)式子就是(x+1)(y+1)sigma(ai,j) - (x+1)sigma(ai,j*j) - (y+1)sigma(ai,j*i) + sigma(ai,j*i*j) 知道怎么處理了沒(méi)，如果沒(méi)有請(qǐng)回去理解一維的處理方法。令 bi,j

10、=ai,j*i ci,j=ai,j*j di,j=ai,j*i*j 維護(hù) a,b,c,d 一共四個(gè)二維樹狀數(shù)組，圓滿地完成了任務(wù)。tyvj p1716就是實(shí)現(xiàn)這兩個(gè)功能的裸題，下面給出完整代碼。/ 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

11、=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

12、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

13、(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%d%d%d,&x