樹(shù)狀數(shù)組在區(qū)間求和問(wèn)題上有大用，其三種復(fù)雜度都比線段樹(shù)要低很多……有關(guān)區(qū)間求和的問(wèn)題主要有以下三個(gè)模型（以下設(shè)A[1..N]為一個(gè)長(zhǎng)為N的序列，初始值為全0）：
（1）“改點(diǎn)求段”型，即對(duì)于序列A有以下操作：
【1】修改操作：將A[x]的值加上c；
【2】求和操作：求此時(shí)A[l..r]的和。
這是最容易的模型，不需要任何輔助數(shù)組。樹(shù)狀數(shù)組中從x開(kāi)始不斷減lowbit(x)（即x&(-x)）可以得到整個(gè)[1..x]的和，而從x開(kāi)始不斷加lowbit(x)則可以得到x的所有前趨。代碼：
void ADD(int x, int c)
{
for (int i=x; i<=n; i+=i&(-i)) a[i] += c;
}
int SUM(int x)
{
int s = 0;
for (int i=x; i>0; i-=i&(-i)) s += a[i];
return s;
}
操作【1】：ADD(x, c);
操作【2】：SUM(r)-SUM(l-1)。
（2）“改段求點(diǎn)”型，即對(duì)于序列A有以下操作：
【1】修改操作：將A[l..r]之間的全部元素值加上c；
【2】求和操作：求此時(shí)A[x]的值。
這個(gè)模型中需要設(shè)置一個(gè)輔助數(shù)組B：B[i]表示A[1..i]到目前為止共被整體加了多少（或者可以說(shuō)成，到目前為止的所有ADD(i, c)操作中c的總和）。
則可以發(fā)現(xiàn)，對(duì)于之前的所有ADD(x, c)操作，當(dāng)且僅當(dāng)x>=i時(shí)，該操作會(huì)對(duì)A[i]的值造成影響（將A[i]加上c），又由于初始A[i]=0，所以有A[i] = B[i..N]之和！而ADD(i, c)（將A[1..i]整體加上c），將B[i]加上c即可——只要對(duì)B數(shù)組進(jìn)行操作就行了。
這樣就把該模型轉(zhuǎn)化成了“改點(diǎn)求段”型，只是有一點(diǎn)不同的是，SUM(x)不是求B[1..x]的和而是求B[x..N]的和，此時(shí)只需把ADD和SUM中的增減次序?qū)φ{(diào)即可（模型1中是ADD加SUM減，這里是ADD減SUM加）。代碼：
void ADD(int x, int c)
{
for (int i=x; i>0; i-=i&(-i)) b[i] += c;
}
int SUM(int x)
{
int s = 0;
for (int i=x; i<=n; i+=i&(-i)) s += b[i];
return s;
}
操作【1】：ADD(l-1, -c); ADD(r, c);
操作【2】：SUM(x)。
（3）“改段求段”型，即對(duì)于序列A有以下操作：
【1】修改操作：將A[l..r]之間的全部元素值加上c；
【2】求和操作：求此時(shí)A[l..r]的和。
這是最復(fù)雜的模型，需要兩個(gè)輔助數(shù)組：B[i]表示A[1..i]到目前為止共被整體加了多少（和模型2中的一樣），C[i]表示A[1..i]到目前為止共被整體加了多少的總和（或者說(shuō)，C[i]=B[i]*i）。
對(duì)于ADD(x, c)，只要將B[x]加上c，同時(shí)C[x]加上c*x即可（根據(jù)C[x]和B[x]間的關(guān)系可得）；
而ADD(x, c)操作是這樣影響A[1..i]的和的：若x<i，則會(huì)將A[1..i]的和加上x(chóng)*c，否則（x>=i）會(huì)將A[1..i]的和加上i*c。也就是，A[1..i]之和 = B[i..N]之和 * i + C[1..i-1]之和。
這樣對(duì)于B和C兩個(gè)數(shù)組而言就變成了“改點(diǎn)求段”（不過(guò)B是求后綴和而C是求前綴和）。
另外，該模型中需要特別注意越界問(wèn)題，即x=0時(shí)不能執(zhí)行SUM_B操作和ADD_C操作！代碼：
void ADD_B(int x, int c)
{
for (int i=x; i>0; i-=i&(-i)) B[i] += c;
}
void ADD_C(int x, int c)
{
for (int i=x; i<=n; i+=i&(-i)) C[i] += x * c;
}
int SUM_B(int x)
{
int s = 0;
for (int i=x; i<=n; i+=i&(-i)) s += B[i];
return s;
}
int SUM_C(int x)
{
int s = 0;
for (int i=x; i>0; i-=i&(-i)) s += C[i];
return s;
}
inline int SUM(int x)
{
if (x) return SUM_B(x) * x + SUM_C(x - 1); else return 0;
}
操作【1】：
ADD_B(r, c); ADD_C(r, c);
if (l > 1) {ADD_B(l - 1, -c); ADD_C(l - 1, -c);}
操作【2】：SUM(r) - SUM(l - 1)。