|
1、概述 樹狀數(shù)組(binary indexed tree)，是一種設計新穎的數(shù)組結構，它能夠高效地獲取數(shù)組中連續(xù)n個數(shù)的和。概括說，樹狀數(shù)組通常用于解決以下問題：數(shù)組{a}中的元素可能不斷地被修改，怎樣才能快速地獲取連續(xù)幾個數(shù)的和？ 2、樹狀數(shù)組基本操作 傳統(tǒng)數(shù)組(共n個元素)的元素修改和連續(xù)元素求和的復雜度分別為O(1)和O(n)。樹狀數(shù)組通過將線性結構轉換成偽樹狀結構（線性結構只能逐個掃描元素，而樹狀結構可以實現(xiàn)跳躍式掃描），使得修改和求和復雜度均為O(lgn)，大大提高了整體效率。 給定序列（數(shù)列）A，我們設一個數(shù)組C滿足 C[i] = A[i–2^k+ 1] + … + A[i] 其中，k為i在二進制下末尾0的個數(shù)，i從1開始算！ 則我們稱C為樹狀數(shù)組。 下面的問題是，給定i，如何求2^k? 答案很簡單：2^k=i&(i^(i-1)) ，也就是i&(-i) 下面進行解釋：
數(shù)組C的具體含義如下圖所示：
當我們修改A[i]的值時，可以從C[i]往根節(jié)點一路上溯，調整這條路上的所有C[]即可，這個操作的復雜度在最壞情況下就是樹的高度即O(logn)。另外，對于求數(shù)列的前n項和，只需找到n以前的所有最大子樹，把其根節(jié)點的C加起來即可。不難發(fā)現(xiàn)，這些子樹的數(shù)目是n在二進制時1的個數(shù)，或者說是把n展開成2的冪方和時的項數(shù),因此，求和操作的復雜度也是O(logn)。 樹狀數(shù)組能快速求任意區(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)。 下面給出樹狀數(shù)組的C語言實現(xiàn)：
3、擴展——二維樹狀數(shù)組 一維樹狀數(shù)組很容易擴展到二維，二維樹狀數(shù)組如下所示： C[x][y] = sum(A[i][j]) 其中，x-lowbit[x]+1 <= i<=x且y-lowbit[y]+1 <= j <=y 4、應用 （1） 一維樹狀數(shù)組： 參見：http://hi.baidu.com/lilu03555/blog/item/4118f04429739580b3b7dc74.html （2） 二維樹狀數(shù)組： 一個由數(shù)字構成的大矩陣，能進行兩種操作 1) 對矩陣里的某個數(shù)加上一個整數(shù)（可正可負） 2) 查詢某個子矩陣里所有數(shù)字的和 要求對每次查詢，輸出結果 5、總結 樹狀數(shù)組最初是在設計壓縮算法時發(fā)現(xiàn)的（見參考資料1），現(xiàn)在也會經常用語維護子序列和。它與線段樹（具體見：數(shù)據(jù)結構之線段樹）比較在思想上類似，比線段樹節(jié)省空間且編程復雜度低，但使用范圍比線段樹小（如查詢每個區(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 ---------------------------------------------------------------------------------------------- 更多關于數(shù)據(jù)結構和算法的介紹，請查看：數(shù)據(jù)結構與算法匯總 ---------------------------------------------------------------------------------------------- 原創(chuàng)文章，轉載請注明： 轉載自董的博客 |
|
|
來自： andersr > 《數(shù)據(jù)結構》
