樹狀數組徹底入門

1. int lowbit(int t)
2. {
3. return t&(-t);
4. }

1. void add(int x,int y)
2. {
3. for(int i=x;i<=n;i+=lowbit(i))
4. tree[i]+=y;
5. }

1. int getsum(int x)
2. {
3. int ans=0;
4. for(int i=x;i>0;i-=lowbit(i))
5. ans+=tree[i];
6. return ans;
7. }

這篇筆記 會詳細的講解，使得隊員們對樹狀數組徹底入門 而不是懵懵懂懂。以上先給出 最常見的，三個函數。(單點更新，區間查詢) 網上的解釋以及分析有很多，這裡是我的一點總結和體會歸納一下，並且在周三(2016.12.07)的講座之後會發布在團隊筆記中， 請隊員們細細閱讀，並且補題。 下面開始*************************************************分割線樹狀數組 重點是在樹狀的數組大家都知道二叉樹吧葉子結點代表A數組A[1]~A[8]

.......現在變形一下

現在定義每一列的頂端結點C[]數組如下圖

C[i]代表 子樹的葉子結點的權值之和// 這裡以求和舉例如圖可以知道C[1]=A[1];C[2]=A[1]+A[2];C[3]=A[3];C[4]=A[1]+A[2]+A[3]+A[4];C[5]=A[5];C[6]=A[5]+A[6];C[7]=A[7];C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];下面觀察如下圖

將C[]數組的結點序號轉化為二進位1=(001) C[1]=A[1];2=(010) C[2]=A[1]+A[2];3=(011) C[3]=A[3];4=(100) C[4]=A[1]+A[2]+A[3]+A[4];5=(101) C[5]=A[5];6=(110) C[6]=A[5]+A[6];7=(111) C[7]=A[7];8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];對照式子可以發現 C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i]; （k為i的二進位中從最低位到高位連續零的長度）例如i=8時，k=3;可以自行帶入驗證;現在引入lowbit(x)lowbit(x) 其實就是取出x的最低位1 換言之 lowbit(x)=2^k k的含義與上面相同 理解一下下面說代碼

1. int lowbit(int t)
2. {
3. return t&(-t);
4. }
5. //-t 代表t的負數 計算機中負數使用對應的正數的補碼來表示
6. //例如 :
7. // t=6（0110） 此時 k=1
8. //-t=-6=(1001+1)=(1010)
9. // t&(-t)=(0010)=2=2^1

C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i];C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+......A[i];*************************************************分割線區間查詢ok 下面利用C[i]數組，求A數組中前i項的和舉個例子 i=7;sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7] ; 前i項和C[4]=A[1]+A[2]+A[3]+A[4]; C[6]=A[5]+A[6]; C[7]=A[7];可以推出: sum[7]=C[4]+C[6]+C[7];序號寫為二進位: sum[(111)]=C[(100)]+C[(110)]+C[(111)];再舉個例子 i=5sum[7]=A[1]+A[2]+A[3]+A[4]+A[5] ; 前i項和C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5];可以推出: sum[5]=C[4]+C[5];序號寫為二進位: sum[(101)]=C[(100)]+C[(101)];細細觀察二進位 樹狀數組追其根本就是二進位的應用結合代碼

1. int getsum(int x)
2. {
3. int ans=0;
4. for(int i=x;i>0;i-=lowbit(i))
5. ans+=C[i];
6. return ans；
7. }

對於i=7 進行演示 7(111) ans+=C[7]lowbit(7)=001 7-lowbit(7)=6(110) ans+=C[6]lowbit(6)=010 6-lowbit(6)=4(100) ans+=C[4]lowbit(4)=100 4-lowbit(4)=0(000) 對於i=5 進行演示 5(101) ans+=C[5]lowbit(5)=001 5-lowbit(5)=4(100) ans+=C[4]lowbit(4)=100 4-lowbit(4)=0(000) *************************************************分割線單點更新當我們修改A[]數組中的某一個值時 應當如何更新C[]數組呢？回想一下 區間查詢的過程，再看一下上文中列出的圖結合代碼分析

1. void add(int x,int y)
2. {
3. for(int i=x;i<=n;i+=lowbit(i))
4. tree[i]+=y;
5. }
6. //可以發現 更新過程是查詢過程的逆過程
7. //由葉子結點向上更新C[]數組

如圖：當更新A[1]時 需要向上更新C[1] ,C[2],C[4],C[8] C[1], C[2], C[4], C[8]寫為二進位C[(001)],C[(010)],C[(100)],C[(1000)] 1(001) C[1]+=A[1]lowbit(1)=001 1+lowbit(1)=2(010) C[2]+=A[1]lowbit(2)=010 2+lowbit(2)=4(100) C[4]+=A[1]lowbit(4)=100 4+lowbit(4)=8(1000) C[8]+=A[1]*************************************************分割線先這樣講解題目:http://poj.org/problem?id=2299 poj2299http://codeforces.com/contest/703/problem/D cf703D來自為知筆記(Wiz)
推薦閱讀：