以前一直對樹狀數組這種結構并不感冒，因為覺得它能做到的事兒線段樹也可以很好的完成。而且線段樹應用更加靈活，可以說比樹狀數組的應用范圍大很多。不過最近碰到兩道題，都可以用樹狀數組這種結構很好的解決，代碼非常精簡單，特別是在二維應用的時候，用線段樹非常麻煩，如果不是必要的話，不應當菜用線段樹這種結構，而應用樹狀數組。稍微研究了下樹狀數組這種結構，寫個總結吧。
樹狀數組它的每個元素并不像普通數組那樣只保存自己的值，而是保存了從它開始前2^k個值的和(k為位置后面的二進制的0的個數）你可以看下圖：
粉線色結點都只保持它自己的值，因為它們的二進制未尾0個數為0。綠色結點都保持了自己與它前一個值的和，藍色結點保存了四個結點的值的和。棕色結點保存了8個結點的值的和。說了這么多，這種結構有什么用？它有什么優勢呢？
它的主要優勢就是可以快速求一段的和，即將求一段和的復雜度降到logN級別的，但是它增了修改一個元素的復雜度，使修改一個元素的復雜度也是logN級別的，不難知道，如果一個應用對于查詢很多，每次查詢都是一個區間的和，那么樹狀數組它的優勢就很明顯了。
問題一：怎么求一段元素的和？如果要求A[i –> j]，顯然如果能快速求A[1->i-1]和A[1->j]那么問題就解決了。怎么快速轉化呢？
因為每個位置它都包含了一段的值，如果這一段值被加進來后，可以快速跳到下一個值，再求。如求A[1->6]，那么知道6包括兩個元素的和，下一次再求4，發現4包括四個元素的和，那么這兩個和加進來就是結果。怎么快速求6的下一個元素呢？這就需要求出它二制后的0的個數的2的次冪，再與6作差即可。如6=(0000 0110)2，所以2^1=2 ,6-2=4, 4=(0000 0100), 所以2^2=4，4-4=0，結束。
int sum(int n) {
int ret = 0;
while(n > 0) {
ret += ss[n];
n -= lowbit(n);
}
return ret;
}
問題二：怎么快速求一個數二進制后面0的個數的2次冪？位運算。兩種方法：x&(-x)或x&(x^(x-1))，它們都利用了位運算的特點，因為我們要求的就是從低位到到高位把遇到的第一個1保持不變，其余各位清0的一個操作！
inline int lowbit(int x) {
return x & (x ^ (x - 1));
}
問題三：怎么快速修改一個元素的值？從上面的圖可以看到，修改一個元素的值，所有包含它的值的元素都會被修改。同樣，它的變化只與求和有一些不同，求和是往下走，而修改值是往上走！
void change(int i, int value) {
while(i <= N) {
ss[i] += value;
i += lowbit(i);
}
}
變形應用：上面應用都是修改一個元素的值，求一段元素的和。那么它還可以進行什么樣的操作呢？修改一段元素都增加或減少一個定值，查詢一個元素的值！同樣是logN級別的。問題是這樣轉化的：如果把a-b區間內的元素都要增加v，那么實際就可以把a元素增加v, b+1減少v，那么查詢a元素的值呢？就是求sum(1->a)所有元素的和就行了！這樣操作是否是正確的？正確性很容易證明，自己在紙上畫畫就會明白了。
二維樹狀數組與一維的情況類似。它也可以進行一段的操作，變形應用也可以。要注意的問題就是修改的值會變成四個角。
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/MasterLuo/archive/2009/12/25/5073784.aspx