|
1、概述 樹狀數組(binary indexed tree)，是一種設計新穎的數組結構，它能夠高效地獲取數組中連續(xù)n個數的和。概括說，樹狀數組通常用于解決以下問題：數組{a}中的元素可能不斷地被修改，怎樣才能快速地獲取連續(xù)幾個數的和？ 2、樹狀數組基本操作 傳統(tǒng)數組(共n個元素)的元素修改和連續(xù)元素求和的復雜度分別為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) 下面進行解釋：
數組C的具體含義如下圖所示：
當我們修改A[i]的值時，可以從C[i]往根節(jié)點一路上溯，調整這條路上的所有C[]即可，這個操作的復雜度在最壞情況下就是樹的高度即O(logn)。另外，對于求數列的前n項和，只需找到n以前的所有最大子樹，把其根節(jié)點的C加起來即可。不難發(fā)現，這些子樹的數目是n在二進制時1的個數，或者說是把n展開成2的冪方和時的項數,因此，求和操作的復雜度也是O(logn)。 樹狀數組能快速求任意區(qū)間的和：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語言實現：
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、總結 樹狀數組最初是在設計壓縮算法時發(fā)現的（見參考資料1），現在也會經常用語維護子序列和。它與線段樹（具體見：數據結構之線段樹）比較在思想上類似，比線段樹節(jié)省空間且編程復雜度低，但使用范圍比線段樹?。ㄈ绮樵兠總€區(qū)間最小值問題）。 6、參考資料 （1） Binary Indexed Trees： http://www./tc?module=Static&d1=tutorials&d2=binaryIndexedTrees （2） 吳豪文章《樹狀數組》： http://www./cwbwebhome/article/article19/zip/treearray.zip （3） 郭煒文章《線段樹和樹狀數組》： http:///summerschool/1_interval_tree.pdf ---------------------------------------------------------------------------------------------- 更多關于數據結構和算法的介紹，請查看：數據結構與算法匯總 ---------------------------------------------------------------------------------------------- 原創(chuàng)文章，轉載請注明： 轉載自董的博客 |
|
|
