數(shù)據(jù)結(jié)構(gòu)與算法_樹狀數(shù)組
問題：
一個包含 n 個數(shù)的數(shù)列 2，7，1，12，5，9，...， 請計(jì)算前 i 個數(shù)的和值，即前綴和 sum[i] = a[1] + a[2] +...+a[i], i = 1,2,...,n。
如何快速的計(jì)算呢？一個一個的加起來嗎？
樹狀數(shù)組，可以高效的計(jì)算數(shù)列前綴和。它的查詢（求前綴和）和更新（修改）操作都可以在O(log n)的時間完成。只擅長單點(diǎn)修改，不擅長區(qū)間修改。
那么樹狀數(shù)組是怎么巧妙地實(shí)現(xiàn)的呢？
1. 樹狀數(shù)組的由來
????樹狀數(shù)組引入了分級管理制度，設(shè)置一個管理小組，管理小組的每個成員管理一個或多個連續(xù)的元素。例如，數(shù)列中有9個元素，分別用 a[1] , a[2], ... , a[9] 表示，設(shè)置一個管理小組 c[ ] ,如圖所示。
（1）查詢前綴和
如果想知道 sum[7] 怎么辦？
只需要 c[7] 加上左側(cè)所有子樹的根即可（把左側(cè)兄弟結(jié)點(diǎn)稱為前驅(qū)），即sum[7] = c[4] +c[6] +c[7]。
（2）修改更新
如果對 a[5] 進(jìn)行修改，令 a[5] 加上一個數(shù) y，那么需要更新改元素的所有祖先結(jié)點(diǎn)。(把祖宗結(jié)點(diǎn)稱為后繼)
2. 樹狀數(shù)組的實(shí)現(xiàn)
樹狀數(shù) 組，又稱為二進(jìn)制索引樹（Binary indexed trees）,通過“二進(jìn)制分解” 劃分區(qū)間。首先要搞清楚：c[i] 保存的是哪些值？
（1）區(qū)間長度
????如果 i 的二進(jìn)制表示末尾有 k 個連續(xù)的 0, 那么 c[i] 保存的值區(qū)間長度為 2^k, 從 a[i] 向前數(shù) 2^k 個元素，如圖所示。
怎么得到這個區(qū)間長度呢？
注：i 取反加一的這個過程就是 -i
在計(jì)算機(jī)中二進(jìn)制數(shù)采用的是補(bǔ)碼表示， -i 的補(bǔ)碼剛好是 i 取反加1，因此 （-i）& i 就是區(qū)間長度。如果 c[i] 保存的值區(qū)間長度用 lowbit(i) 表示，則 lowbit(i) = (-i) & i 。
算法代碼：
int lowbit(int i){
????return (-i)&i ;
}
(2) 前驅(qū)和后繼
直接前驅(qū)： c[i] 的直接前驅(qū)為 c[i-lowbit(i)] , 即 c[i] 左側(cè)緊鄰的子樹的根；
直接后繼： c[i] 的直接后繼為 c[i+lowbit(i)], 即 c[i] 的父親；
前驅(qū)： c[i] 的直接前驅(qū)，其直接前驅(qū)的直接前驅(qū)， ... , 即 c[i] 左側(cè)所有的子樹的根；
后繼: c[i] 的直接后繼，其直接后繼的直接后繼， ... , c[i] 的父親，其父親的父親，即c[i] 的所有祖先。
?
（3）查詢前綴和
????求前 i 個元素的前綴和 sum[i] 就等于 c[i] 加上 c[i] 的前綴。例如，sum[7] 就等于 c[7] 加上 c[7] 的前驅(qū)， c[7] 的前驅(qū) 為 c[6] ，c[4]，因此即 sum[7] = c[7] +c[6] + c[4]。
算法代碼：
(4) 修改更新
????如果對 a[i] 進(jìn)行修改，令 a[i] 加上一個數(shù) z, 只需要更新 c[i] 及其后繼（祖先），即令這些結(jié)點(diǎn)都加上 z 即可，其他結(jié)點(diǎn)不需要修改。例如，修改 a[5] , 加上2 ，只需要 c[5]+2, c[5]的后繼分別加上2，即 c[6] +2, c[8] +2。
算法代碼：
void add(int i, int z) //a[i] 加上 z
{
? ?for(;i<n;i+=lowbit(i))
????{
????????c[i] +=z;
????}
}
注意：樹狀數(shù)組下標(biāo)從1 開始，不能從 0 開始，因?yàn)?lowbit(0) = 0，會出現(xiàn)死循環(huán)。
（5）查詢區(qū)間和
????如果求區(qū)間和值 a[i] + a[i+1] + ... + a[j] ,則求解前 j 個元素的和值減去前 i-1 個元素的和值即可， sum[j] -sum[i-1]。
????算法代碼：
????
3. 樹狀數(shù)組的性能分析
????樹狀數(shù)組又稱為二進(jìn)制索引樹（Binary indexed trees），是通過“二進(jìn)制分解”劃分區(qū)間的。樹狀數(shù)組的性能和 n的二進(jìn)制位數(shù)有關(guān)，n的二進(jìn)制位數(shù)為 [log n] ， [x] 表示取下限加一。
????
4. 多維樹狀數(shù)組
????前面已經(jīng)知道一維樹狀數(shù)組修改和查詢的時間復(fù)雜度均為 O(log n),可以擴(kuò)展為 m 維樹狀數(shù)組，其時間復(fù)雜度為 O(log^m n)。算法只需要加上一層循環(huán)即可。
例如，二維數(shù)組 a[n][n], 樹狀數(shù)組為 c[ ][ ]，那么其查詢和修改的方法如下：
（1）查詢前綴和
????二維數(shù)組的前綴和其實(shí)是計(jì)算從數(shù)組左上角到當(dāng)前位置（x,y）矩陣的區(qū)間和，只需要在一維數(shù)組查詢前綴和的代碼加上一層循環(huán)即可。
（2）修改更新
????如果對 a[x][y] 進(jìn)行修改，令 a[x][y] 加上一個數(shù) z, 只需要在一維數(shù)組更新的代碼加上一層循環(huán)即可。
算法代碼：
（3）查詢區(qū)間和值
????二維數(shù)組查詢區(qū)間和值，其實(shí)是求左上角（x1,y1）到右下角（x2,y2）子矩陣區(qū)間和，如圖所示。
算法代碼：
5.樹狀數(shù)組的局限性
