參考自:http://www.cnblogs.com/huangxincheng/archive/2012/12/05/2802858.html

0. 介紹(來自wikipedia)

　　- 樹狀數(shù)組, 又稱二分索引樹(Binary Indexed Tree, BIT), 用于高效計算數(shù)列的前綴和.

　　-?它可以以的時間得到，并同樣以對某項加一個常數(shù)。

1. 數(shù)據(jù)結構定義

　　- 存放原始數(shù)據(jù)元素的數(shù)組a (i.e. ?int[] ?a)

　　- 樹狀數(shù)組 s ? (i.e. ? int[] s)

　　- 注意:

　　　　-?原始數(shù)據(jù)數(shù)組 a 可能是隱含的, 因為 s[i] 中包含a[i], 而且也可以通過 s[i]-s[i-1] 來計算得到 a[i].

　　　　- 樹狀數(shù)組s只是一個維護 a 信息的數(shù)據(jù)結構, 可能本身不對應實際的物理含義, 是一種抽象的結構.

2. 說明:

　　- s 和 a 的大小一樣大

　　- 當a全為0 的時候, s也全為0.

　　- s 的build 是基于維護a的, 但是a不一定是現(xiàn)成的, 有時候可能通過從0開始動態(tài)構建(參考題解poj 2352).

　　- 下標從 1 開始計算, 因為后面要用到二進制格式末尾 連續(xù)0 的個數(shù). 所以如果用 0 的話不太好處理.

3. 公式(2個等效的, 公式1用于理解, 計算主要用公式2)

　　- 1.?s[i]=a[i-2^k+1]+a[i-2^k+1+1]+......+a[i-1]+a[i] ? (if i-2^k+1 < i?) ??

　 ? - 2. s[i]=a[i] + s[j] ? (j=?i-1 decreasing to?i-2^k+1?, j -=?2^t, t=lowbit(j)?)

　　　 ?- s[i] 表示 樹狀數(shù)組第i個元素, ?并不是前 i 個元素的和.

　　　　- k 表示 i 的二進制格式的末尾連續(xù)0的位數(shù)( i.e. ? ?i=6₁₀=110_2?? => k = 1) , 也代表s[i] 在樹狀結構中的層數(shù) (i.e. ?s[6] 在 level 1, ?from level 0).

　　　　- 2^k?表示 s[i] 中包含原始數(shù)據(jù) 數(shù)組 a 中的元素個數(shù) ?如s[6] = a[5] + a[6], 因為 k=1, ?2^k為2, 利用公式計算得到 a[5] 和 a[6]. ?a[i-2^k+1] 算出 a[5]為起始項.

4. 工具代碼

　　- 求 2^k??值

int lowbit(int x){return x & (-x); }

　　- 建立樹狀數(shù)組

　　　　- 注意: 只有當原始數(shù)據(jù)數(shù)組準備好之后才能用這個方法. 如果沒有, 應該使用動態(tài)構建(先初始化s, 然后根據(jù)條件構建s到完整的樹狀數(shù)組).

//根據(jù)原始數(shù)據(jù)數(shù)組建立樹狀數(shù)組 s void build(){for (int i=1;i<=MAX_N;i++){ // s(i) 為計算的目標值s[i]=a[i]; // 基礎值, s(i)必定包含 a(i)// 根據(jù)公式2, 倒著加回去, 從s(i-1) 加回去到 i-2^k+1. for (int j=i-1; j>=i-lowbit(i)+1;j-=lowbit(j)) //j每次減去的是j二進制中的每一位, 所以這個循環(huán)復雜度是O(logn)s[i]+=s[j];} }

?

　　- 查詢: 求前n項和, 繼而也可以求任意區(qū)間之和. (logN)

//計算前n項和 int sumn (int n){int sum = 0;//利用公式進行計算.for (int i = n; i > 0; i -= lowbit(i)) sum += s[i];return sum; }

　　- 修改: 修改元素數(shù)據(jù)并同步更新樹狀數(shù)組的值.(logN)

//原始數(shù)組可以直接修改, 更新樹狀數(shù)組需要將包含 a[i]的所有元素更新. // @param index: 修改的元素的下標. a[i]的修改對s[i]以前的元素沒有影響. // @param dalta : 修改量 void modify(int index, int delta){for (int j = index; j <= MAX_N; j += lowbit(j))s[j] += delta; }

?

轉載于:https://www.cnblogs.com/roger9567/p/4866792.html

總結

以上是生活随笔為你收集整理的树状数组学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。