1 概述


2 3 　　樹狀數(shù)組是一個查詢和修改復雜度都為log(n)的數(shù)據(jù)結構，假設數(shù)組a[1..n]， 用lowbit函數(shù)維護了一個樹的結構那么查詢a[1]+...+a[n]的時間是log級別的，而且是一個在線的數(shù)據(jù)結構， 4 　　支持隨時修改某個元素的值，復雜度也為log級別。 5 　　來觀察這個圖： 6 　　令這棵樹的結點編號為C1，C2...Cn。令每個結點的值為這棵樹的值的總和，那么容易發(fā)現(xiàn)： 7 　　C1 = A1 8 　　C2 = A1 + A2 9 　　C3 = A3 10 　　C4 = A1 + A2 + A3 + A4 11 　　C5 = A5 12 　　C6 = A5 + A6 13 　　C7 = A7 14 　　C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 15 　　... 16 　　C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16 17 　　這里有一個有趣的性質(zhì)： 18 　　設節(jié)點編號為x，那么這個節(jié)點管轄的區(qū)間為2^k（其中k為x二進制末尾0的個數(shù)）個元素。因為這個區(qū)間最后一個元素必然為Ax， 19 　　所以很明顯：Cn = A(n – 2^k + 1) + ... + An 20 　　算這個2^k有一個快捷的辦法，定義一個函數(shù)如下即可： 21 　　int lowbit(int x){ 22 　　return x&(x^(x–1)); 23 　　} 24 　　當想要查詢一個SUM(n)(求a[n]的和），可以依據(jù)如下算法即可： 25 　　step1:　令sum = 0，轉(zhuǎn)第二步； 26 　　step2:　假如n <= 0，算法結束，返回sum值，否則sum = sum + Cn，轉(zhuǎn)第三步； 27 　　step3: 令n = n – lowbit(n)，轉(zhuǎn)第二步。 28 　　可以看出，這個算法就是將這一個個區(qū)間的和全部加起來，為什么是效率是log(n)的呢？以下給出證明： 29 　　n = n – lowbit(n)這一步實際上等價于將n的二進制的最后一個1減去。而n的二進制里最多有l(wèi)og(n)個1，所以查詢效率是log(n)的。 30 　　那么修改呢，修改一個節(jié)點，必須修改其所有祖先，最壞情況下為修改第一個元素，最多有l(wèi)og(n)的祖先。 31 　　所以修改算法如下（給某個結點i加上x）： 32 　　step1: 當i > n時，算法結束，否則轉(zhuǎn)第二步； 33 　　step2: Ci = Ci + x， i = i + lowbit(i)轉(zhuǎn)第一步。 34 　　i = i +lowbit(i)這個過程實際上也只是一個把末尾1補為0的過程。 35 　　對于數(shù)組求和來說樹狀數(shù)組簡直太快了! 1 int lowbit(int x) 2 { 3 return x&(-x); 4 } 5 6 7 int sum(int k) 8 { 9 int ans=0; 10 while(k>0) 11 { 12 ans+=c[k]; 13 k=k-lowbit(k); 14 } 15 return ans; 16 } 17 18 19 int add(int pos ,int num) 20 { 21 while(pos<=n) 22 { 23 c[pos]+=num; 24 pos+=lowbit(pos); 25 } 26 }

?

與線段樹的比較樹狀數(shù)組是一個可以很高效的進行區(qū)間統(tǒng)計的數(shù)據(jù)結構。在思想上類似于線段樹，比線段樹節(jié)省空間，編程復雜度比線段樹低，但適用范圍比線段樹小。以簡單的求和為例。設原數(shù)組為a[1..N]，樹狀數(shù)組為c[1..N]，其中c[k] = a[k-(2^t)+1] + ... + a[k]。比如c[6] = a[5] + a[6]。也就是說，把k表示成二進制1***10000，那么c[k]就是1***00001 + 1***00010 + ... + 1***10000這一段數(shù)的和。設一個函數(shù)lowestbit(k)為取得k的最低非零位，容易發(fā)現(xiàn)，根據(jù)上面的表示方法，從a[1]到a[k]的所有數(shù)的總和即為sum[k] = c[k] + c[k-lowestbit(k)] + c[k-lowestbit(k)-lowestbit(k-lowestbit(k))] + ... 于是可以在logk的時間內(nèi)求出sum[k]。當數(shù)組中某元素發(fā)生變化時，需要改動的c值是c[k],c[k+lowestbit(k)], c[k+lowestbit(k)+lowestbit(k+lowestbit(k))] ... 這個復雜度是logN (N為最大范圍)擴展到多維情況：以二維為例，用c[k1][k2]表示c[k1-(2^t1)+1][k2-(2^t2)+1] + ... + c[k1][k2]的總和。可以用類似的方法進行處理。復雜度為(logn)^k (k為維數(shù))樹狀數(shù)組相比線段樹的優(yōu)勢：空間復雜度略低，編程復雜度低，容易擴展到多維情況。劣勢：適用范圍小，對可以進行的運算也有限制，比如每次要查詢的是一個區(qū)間的最小值，似乎就沒有很好的解決辦法。多維情況的幾道題目:POJ 2155 MatrixURAL 1470 UFOs其中POJ 2155是一道很不錯的題目，表面上看，這題的要求似乎和樹狀數(shù)組的使用方法恰好相反，改變的是一個區(qū)間，查詢的反而是一個點。實際上可以通過一個轉(zhuǎn)化巧妙的解決。首先對于每個數(shù)A定義集合up(A)表示{A, A+lowestbit(A), A+lowestbit(A)+lowestbit(A+lowestbit(A))...} 定義集合down(A)表示{A, A-lowestbit(A), A-lowestbit(A)-lowestbit(A-lowestbit(A)) ... , 0}?？梢园l(fā)現(xiàn)對于任何A<B，up(A)和down(B)的交集有且僅有一個數(shù)。于是對于這道題目來說，翻轉(zhuǎn)一個區(qū)間[A,B]（為了便于討論先把原問題降為一維的情況），我們可以把down(B)的所有元素的翻轉(zhuǎn)次數(shù)+1，再把down(A-1)的所有元素的翻轉(zhuǎn)次數(shù)-1。而每次查詢一個元素C時，只需要統(tǒng)計up(C)的所有元素的翻轉(zhuǎn)次數(shù)之和，即為C實際被翻轉(zhuǎn)的次數(shù)。實際實現(xiàn)時，由于只考慮奇偶，因此無須統(tǒng)計確切的翻轉(zhuǎn)次數(shù)。另外，如果翻轉(zhuǎn)up(A)和up(B+1)，查詢down(C)，也是同樣的效果。這種方法可以很容易地擴展到二維情況。比起線段樹、四分樹之類的常規(guī)思路，無論編程復雜度還是常數(shù)速度上都有很大優(yōu)勢。 二維樹狀數(shù)組：int lowbit(int x) {return x&(-x); }void add(int x,int y,int d)//或for循環(huán) s 是節(jié)點個數(shù) {int i=x;int j=y;while(i<=s){j=y;while(j<=s){map[i][j]+=d;j=j+lowbit(j);}i=i+lowbit(i);} }int sum(int l,int b) {int i=l;int j=b;int ans=0;while(i>0){j=b;while(j>0){ans+=map[i][j];j-=lowbit(j);}i-=lowbit(i);}return ans; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/acSzz/archive/2012/04/20/2459573.html

總結

以上是生活随笔為你收集整理的树状数组 讲解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。