樹狀數(shù)組(Binary Indexed Tree)是又一種靜態(tài)的樹結(jié)構(gòu)。它的首要用途是用于維護(hù)前綴和，也即：一數(shù)組a[1..n]，隨時(shí)會(huì)改變其中某a[i]，還會(huì)詢問s[i]=a[1]+a[2]+…+a[i]，樹狀數(shù)組可完美解決這一問題。
定義數(shù)組c[0..n]，其中c[i]=a[i-2^k+1]+a[i-a^k+2]+…+a[i]，其中k為i在二進(jìn)制下末尾0的個(gè)數(shù)。當(dāng)我們改變一個(gè)a[i]時(shí)，會(huì)有很多c[i]隨之改變；若需查詢某個(gè)s[i]，需要累加多個(gè)c[i]。好在確定需要改變或累加的元素都可以用比較簡(jiǎn)便的方法得出，這方法的核心就是lowbit值。
定義lowbit(x)=x&(x^(x-1))，它相當(dāng)于將最右邊的1左邊的東西全部去掉。若需改變a[i]，則c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……就是需要改變的c數(shù)組中的元素。若需查詢s[i]，則c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c數(shù)組中的元素。這看上去有些玄妙，我覺得其實(shí)也可以不用透徹理解。
一維的樹狀數(shù)組的每個(gè)操作的復(fù)雜度都是O(logn)的，非常高效。它可以擴(kuò)充為n維，這樣每個(gè)操作的復(fù)雜度就變成了O((logn)^n)，在n不大的時(shí)候仍然完全可以接受。擴(kuò)充的方法就是將原來改變和查詢的函數(shù)中的一個(gè)循環(huán)改成嵌套的n個(gè)循環(huán)在n維的c數(shù)組中操作。
要注意樹狀樹組能處理的是下標(biāo)為1..n的數(shù)組，絕對(duì)不能出現(xiàn)下標(biāo)為0的情況。因?yàn)閘owbit(0)=0，這樣會(huì)陷入死循環(huán)。對(duì)于我這個(gè)從來都用C語言思考的家伙來說，這一點(diǎn)格外需要注意。
似乎樹狀數(shù)組也可以用來解決一些與前綴和關(guān)聯(lián)不大的問題，例如NOI2004的cashier，但我還不太會(huì)（那題我只會(huì)用平衡樹或線段樹或虛二叉樹解）。
示例程序：ural1470.cpp（三維的樹狀數(shù)組）
附：
【引言】
在解題過程中，我們有時(shí)需要維護(hù)一個(gè)數(shù)組的前綴和S[i]=A[1]+A[2]+...+A[i]。
但是不難發(fā)現(xiàn)，如果我們修改了任意一個(gè)A[i],S[i]、S[i+1]...S[n]都會(huì)發(fā)生變化。
可以說，每次修改A[i]后，調(diào)整前綴和S[]在最壞情況下會(huì)需要O(n)的時(shí)間。
當(dāng)n非常大時(shí)，程序會(huì)運(yùn)行得非常緩慢。
因此，這里我們引入“樹狀數(shù)組”，它的修改與求和都是O(logn)的，效率非常高。
【理論】
為了對(duì)樹狀數(shù)組有個(gè)形 象的認(rèn)識(shí)，我們先看下面這張圖。
如圖所示，紅色矩形表示的數(shù)組C[]就是樹狀數(shù)組。
這里，C[i]表示A[i-2^k+1]到A[i]的和，而k則是i在二進(jìn)制時(shí)末尾0的個(gè)數(shù)，
或者說是i用2的冪方和表示時(shí)的最小指數(shù)。
（ 當(dāng)然，利用位運(yùn)算，我們可以直接計(jì)算出2^k=i&(i^(i-1)) ）
同時(shí)，我們也不難發(fā)現(xiàn)，這個(gè)k就是該節(jié)點(diǎn)在樹中的高度，因而這個(gè)樹的高度不會(huì)超過logn。
所以,當(dāng)我們修改A[i]的值時(shí)，可以從C[i]往根節(jié)點(diǎn)一路上溯，調(diào)整這條路上的所有C[]即可，
這個(gè)操作的復(fù)雜度在最壞情況下就是樹的高度即O(logn)。
另外，對(duì)于求數(shù)列的前n項(xiàng)和，只需找到n以前的所有最大子樹，把其根節(jié)點(diǎn)的C加起來即可。
不難發(fā)現(xiàn)，這些子樹的數(shù)目是n在二進(jìn)制時(shí)1的個(gè)數(shù)，或者說是把n展開成2的冪方和時(shí)的項(xiàng)數(shù),
因此，求和操作的復(fù)雜度也是O(logn)。
接著，我們考察這兩種操作下標(biāo)變化的規(guī)律：
首先看修改操作：
已知下標(biāo)i，求其父節(jié)點(diǎn)的下標(biāo)。
我們可以考慮對(duì)樹從邏輯上轉(zhuǎn)化：
如圖，我們將子樹向右對(duì)稱翻折，虛擬出一些空白結(jié)點(diǎn)（圖中白色），將原樹轉(zhuǎn)化成完全二叉樹。
有圖可知，對(duì)于節(jié)點(diǎn)i，其父節(jié)點(diǎn)的下標(biāo)與翻折出的空白節(jié)點(diǎn)下標(biāo)相同。
因而父節(jié)點(diǎn)下標(biāo) p=i+2^k (2^k是i用2的冪方和展開式中的最小冪，即i為根節(jié)點(diǎn)子樹的規(guī)模)
即 p = i + i&(i^(i-1)) 。
接著對(duì)于求和操作：
因?yàn)槊靠米訕涓采w的范圍都是2的冪，所以我們要求子樹i的前一棵樹，只需讓i減去2的最小冪即可。
即 p = i - i&(i^(i-1)) 。
至此，我們已經(jīng)比較詳細(xì)的分析了樹狀數(shù)組的復(fù)雜度和原理。
在最后，我們將給出一些樹狀數(shù)組的實(shí)現(xiàn)代碼，希望讀者能夠仔細(xì)體會(huì)其中的細(xì)節(jié)。
【代碼】
求最小冪2^k:
int Lowbit(int t)
{
return t & ( t ^ ( t - 1 ) );
}
|
求前n項(xiàng)和：
int Sum(int end)
{
int sum = 0;
while(end > 0)
{
sum += in[end];
end -= Lowbit(end);
}
return sum;
}
|
對(duì)某個(gè)元素進(jìn)行加法操作：
void plus(int pos , int num)
{
while(pos <= n)
{
in[pos] += num;
pos += Lowbit(pos);
}
}
|