1、概述

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

2、樹狀數組基本操作

傳統數組(共n個元素)的元素修改和連續元素求和的復雜度分別為O(1)和O(n)。樹狀數組通過將線性結構轉換成偽樹狀結構（線性結構只能逐個掃描元素，而樹狀結構可以實現跳躍式掃描），使得修改和求和復雜度均為O(lgn)，大大提高了整體效率。

給定序列（數列）A，我們設一個數組C滿足

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

其中，k為i在二進制下末尾0的個數，i從1開始算！

則我們稱C為樹狀數組。

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

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

下面進行解釋：

以i=6為例（注意：a_x表示數字a是x進制表示形式）：

(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]

數組C的具體含義如下圖所示：

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

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

下面給出樹狀數組的C語言實現：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

//求2^k intlowbit(intt) { ????returnt & ( t ^ ( t - 1 ) ); } //求前n項和 intsum(intend) { ???intsum = 0; ???while(end > 0) ??{ ?????sum += in[end]; ?????end -= lowbit(end); ??} ??returnsum; } //增加某個元素的大小 voidplus(intpos, intnum) { ???while(pos <= n) ??{ ?????in[pos] += num; ?????pos += lowbit(pos); ??} }

3、擴展——二維樹狀數組

一維樹狀數組很容易擴展到二維，二維樹狀數組如下所示：

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

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

4、應用

（1）??? 一維樹狀數組：

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

（2）??? 二維樹狀數組：

一個由數字構成的大矩陣，能進行兩種操作

1) 對矩陣里的某個數加上一個整數（可正可負）

2) 查詢某個子矩陣里所有數字的和

要求對每次查詢，輸出結果

5、總結

樹狀數組最初是在設計壓縮算法時發現的（見參考資料1），現在也會經常用語維護子序列和。它與線段樹（具體見：數據結構之線段樹）比較在思想上類似，比線段樹節省空間且編程復雜度低，但使用范圍比線段樹小（如查詢每個區間最小值問題）。

6、參考資料

（1）??? Binary Indexed Trees：

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

（2）??? 吳豪文章《樹狀數組》：

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

（3）??? 郭煒文章《線段樹和樹狀數組》：

http://poj.org/summerschool/1_interval_tree.pdf

---------------------------------------------------------------------------------------------- 更多關于數據結構和算法的介紹，請查看：數據結構與算法匯總 ----------------------------------------------------------------------------------------------

原創文章，轉載請注明：?轉載自董的博客

本文鏈接地址:?http://dongxicheng.org/structure/binary_indexed_tree/

總結

以上是生活随笔為你收集整理的数据结构之树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。