1、概述

樹狀數(shù)組(binary indexed tree)，是一種設(shè)計(jì)新穎的數(shù)組結(jié)構(gòu)，它能夠高效地獲取數(shù)組中連續(xù)n個(gè)數(shù)的和。概括說，樹狀數(shù)組通常用于解決以下問題：數(shù)組{a}中的元素可能不斷地被修改，怎樣才能快速地獲取連續(xù)幾個(gè)數(shù)的和？

2、樹狀數(shù)組基本操作

傳統(tǒng)數(shù)組(共n個(gè)元素)的元素修改和連續(xù)元素求和的復(fù)雜度分別為O(1)和O(n)。樹狀數(shù)組通過將線性結(jié)構(gòu)轉(zhuǎn)換成偽樹狀結(jié)構(gòu)（線性結(jié)構(gòu)只能逐個(gè)掃描元素，而樹狀結(jié)構(gòu)可以實(shí)現(xiàn)跳躍式掃描），使得修改和求和復(fù)雜度均為O(lgn)，大大提高了整體效率。

給定序列（數(shù)列）A，我們?cè)O(shè)一個(gè)數(shù)組C滿足

C[i] = A[i–2^k+ 1] + … + A[i]

其中，k為i在二進(jìn)制下末尾0的個(gè)數(shù)，i從1開始算！

則我們稱C為樹狀數(shù)組。

下面的問題是，給定i，如何求2^k?

答案很簡(jiǎn)單：2^k=i&(i^(i-1)) ，也就是i&(-i)

下面進(jìn)行解釋：

以i=6為例（注意：a_x表示數(shù)字a是x進(jìn)制表示形式）：

(i)_10 = (0110)_2

(i-1)_10=(0101)_2

i xor (i-1) =(0011)_2

i and (i xor (i-1))  =(0010)_2

2^k = 2

C[6] = C[6-2+1]+…+A[6]=A[5]+A[6]

數(shù)組C的具體含義如下圖所示：

當(dāng)我們修改A[i]的值時(shí)，可以從C[i]往根節(jié)點(diǎn)一路上溯，調(diào)整這條路上的所有C[]即可，這個(gè)操作的復(fù)雜度在最壞情況下就是樹的高度即O(logn)。另外，對(duì)于求數(shù)列的前n項(xiàng)和，只需找到n以前的所有最大子樹，把其根節(jié)點(diǎn)的C加起來即可。不難發(fā)現(xiàn)，這些子樹的數(shù)目是n在二進(jìn)制時(shí)1的個(gè)數(shù)，或者說是把n展開成2的冪方和時(shí)的項(xiàng)數(shù),因此，求和操作的復(fù)雜度也是O(logn)。

樹狀數(shù)組能快速求任意區(qū)間的和：A[i] + A[i+1] + … + A[j]，設(shè)sum(k) = A[1]+A[2]+…+A[k]，則A[i] + A[i+1] + … + A[j] = sum(j)-sum(i-1)。

下面給出樹狀數(shù)組的C語言實(shí)現(xiàn)：

3、擴(kuò)展——二維樹狀數(shù)組

一維樹狀數(shù)組很容易擴(kuò)展到二維，二維樹狀數(shù)組如下所示：

C[x][y] = sum(A[i][j])

其中，x-lowbit[x]+1 <= i<=x且y-lowbit[y]+1 <= j <=y

4、應(yīng)用

（1）    一維樹狀數(shù)組：

參見：http://hi.baidu.com/lilu03555/blog/item/4118f04429739580b3b7dc74.html

（2）    二維樹狀數(shù)組：

一個(gè)由數(shù)字構(gòu)成的大矩陣，能進(jìn)行兩種操作

1) 對(duì)矩陣?yán)锏哪硞€(gè)數(shù)加上一個(gè)整數(shù)（可正可負(fù)）

2) 查詢某個(gè)子矩陣?yán)锼袛?shù)字的和

要求對(duì)每次查詢，輸出結(jié)果

5、總結(jié)

樹狀數(shù)組最初是在設(shè)計(jì)壓縮算法時(shí)發(fā)現(xiàn)的（見參考資料1），現(xiàn)在也會(huì)經(jīng)常用語維護(hù)子序列和。它與線段樹（具體見：數(shù)據(jù)結(jié)構(gòu)之線段樹）比較在思想上類似，比線段樹節(jié)省空間且編程復(fù)雜度低，但使用范圍比線段樹?。ㄈ绮樵兠總€(gè)區(qū)間最小值問題）。

6、參考資料

（1）    Binary Indexed Trees：

http://www./tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

（2）    吳豪文章《樹狀數(shù)組》：

http://www./cwbwebhome/article/article19/zip/treearray.zip

（3）    郭煒文章《線段樹和樹狀數(shù)組》：

http:///summerschool/1_interval_tree.pdf

----------------------------------------------------------------------------------------------
更多關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的介紹，請(qǐng)查看：數(shù)據(jù)結(jié)構(gòu)與算法匯總
----------------------------------------------------------------------------------------------