-
樹狀數組
鎖定
樹狀數組或二叉索引樹(英語:Binary Indexed Tree),又以其發明者命名為Fenwick樹,最早由Peter M. Fenwick於1994年以A New Data Structure for Cumulative Frequency Tables為題發表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決數據壓縮裏的累積頻率(Cumulative Frequency)的計算問題,現多用於高效計算數列的前綴和, 區間和。
- 中文名
- 樹狀數組
- 外文名
- Binary Indexed Tree
- 應用範圍
- 信息學
- 功 能
- 區間和查詢、單點修改
- 時間複雜度
- log(n)
樹狀數組簡介
樹狀數組或二叉索引樹(英語:Binary Indexed Tree),又以其發明者命名為Fenwick樹,最早由Peter M. Fenwick於1994年以A New Data Structure for Cumulative Frequency Tables為題發表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決數據壓縮裏的累積頻率(Cumulative Frequency)的計算問題,現多用於高效計算數列的前綴和, 區間和。
[1]
樹狀數組結構起源
按照Peter M. Fenwick的説法,正如所有的整數都可以表示成2的冪和,我們也可以把一串序列表示成一系列子序列的和。採用這個想法,我們可將一個前綴和劃分成多個子序列的和,而劃分的方法與數的2的冪和具有極其相似的方式。一方面,子序列的個數是其二進制表示中1的個數,另一方面,子序列代表的f[i]的個數也是2的冪。
[1]
樹狀數組基本操作
樹狀數組預備函數
定義一個Lowbit函數,返回參數轉為二進制後,最後一個1的位置所代表的數值.
例如,Lowbit(34)的返回值將是2;而Lowbit(12)返回4;Lowbit(8)返回8。
將34轉為二進制,為0010 0010,這裏的"最後一個1"指的是從
位往前數,見到的第一個1,也就是
位上的1.
程序上,((Not I)+1) And I表明了最後一位1的值,
仍然以34為例,Not 0010 0010的結果是 1101 1101(221),加一後為 1101 1110(222), 把 0010 0010與1101 1110作AND,得0000 0010(2)。
[1]
樹狀數組應用
樹狀數組求逆序數
逆序數是一個數列中在它前面有比它大的個數。如4312的逆序數是0+1+2+2=5。