樹狀數組
By 岩之痕
一、概述
樹狀數組是一種 用數組進行存儲的 自下而上進行操作的 多叉樹。
以下叙述中，A為原數組，C為樹狀數組所用的數組，B為特殊情況需要用到的輔助數組。
最基本的應用就是維護一個支援兩種操作的數列：1.讓A[i]加上某數X 2.求一個區間A[L] + A[L+1] + ... + A[R] 的和。
樹狀數組可以做到兩個操作的時間複雜度都是O(log2(n))，而且一般比線段樹快。
樹狀數組下标從1開始。
二、建樹 (圖中以n=11的數組為例進行建樹)
令C數組的每個元素與A數組相等，這時的C稱為第一行,見下圖：（操作11次）
然後把第一行的C中，奇數項不動，偶數項每個加上自己的前一項。即C[2]+=C[1],C[4]+=C[3], C[6]+=C[5]......（操作5次）見下圖：
上圖第一行就是最終的C數組的值了，這時對第二行進行同樣的操作，也就是偶數項都加上自己的前一項，C[4]+=C[2],C[8]+=C[6],.....（操作2次）見下圖：
上圖第二行剩下的數也是最終的C的值了，然後對第三行進行同樣的操作：C[8]+=C[4]... （操作1次）下圖是最終形成的數組，明顯看出這是一顆無根的多叉樹。
圖一：n=11的建好之後的樹狀數組
建樹代碼：
void Build(int n){//運作函數之前C數組的每個數都等于A數組的每個數
int X=2,HalfX=1;
while(X <= n){
for(int i=X;i<=n;i+=X){
C[i]+=C[i-HalfX];
}
X <<= 1;HalfX <<= 1;
}
} 這樣理論上操作次數是 2*n - count_bits(n) , 其中count_bits(n)傳回n的二進制表示中1的個數。
對于n=11 的情況 2*11 - count_bits(11) = 19 次。 若不保留A數組，直接将A數組變成C數組，那麼操作次數就是 n - count_bits(n) （少了第一次的n個指派）.
總之是O(n)的建樹。
但是一般更簡單的寫法是先清空C數組，然後調用n次Add(i,A[i])函數，這樣時間複雜度是O(n*log2(n)) 。
很奇怪的是，在用HDU1166（點修改區間查詢）這道題進行測試的時候，第一種方法反而比第二種慢，沒想通。
不過，這麼建樹還是有好處的，比如在 做動态區間第k大的時候，用樹狀數組套可持久化線段樹這種方法的話，
這麼建樹的空間消耗是明顯小于調用n次Add的。又或者，如果維護的性質的“加法”很耗時間的話，也可以考慮直接建樹。
三、Add 函數（修改某一項）
首先來了解如何對上述數組進行修改（下圖中沿着斜線向上走，經過的節點都要修改）。
再來看一下上面最後一張圖：
注意到：
第 1 行C的下标為1*(1,3,5,7,...) 1的父節點是2。3的父節點是4。5的父節點是6。7的父節點是8。9的父節點是10. 每個C存了1個A中的數
第 2 行C的下标為2*(1,3,5,7,..) 下标除掉2以後，1的父節點是2。3的父節點是4。 每個C存了2個A中的數
第 3 行C的下标為4*(1,3,5,7...) 下标除掉4以後，1的父節點是2。 每個C存了4個A中的數
第k+1行C的下标為2^k*(1,3,5,7..) 下标除掉2^k以後，1的父節點是2。3的父節點是4等等 每個C存了2^k個A中的數
現在問題就是拿到一個下标 x ，怎麼去找 x 的父節點的問題（因為更新完x，也必須去更新x的父節點）
假設 x = （2^k） * 某奇數 ，則根據上述規律， x 的父節點下标其實是: （某奇數+1）* (2^k) = 某奇數*(2^k) + (2^k) = ｘ+ (2^k)
于是隻要通過 x 快速找到這個 (2^k) 就可以找到 x 的父節點了，而樹狀數組中很重要的函數lowbit 剛好就可以求出 (2^k)
即，若 x = （2^k） * 某奇數 則 lowbit(x) = 2^k (關于這部分内容去看第五部分：lowbit 函數)
于是就不難看懂如下Add代碼：
void Add(int x,int c){
if(!x) return;//防止死循環
while(x <= n){
C[x]+=c;
x+=lowbit(x);
}
} 四：Sum函數（求前x項的和）
Sum中x節點存的數的個數是lowbit(x)，
C[x]=A[x-lowbit(x)+1] + A[x-lowbit(x)+2] +..+A[x-1]+A[x]
是以結果加上了C[x]之後，緊接着是要去找C[x-lowbit(x)]的值，于是不難看懂如下Sum代碼：
int Sum(int x){//前x項的和
int ANS=0;
while(x>0){
ANS+=C[x];
x-=lowbit(x);
}
return ANS;
} 五：lowbit函數
首先是lowbit的定義：
int lowbit(int x) { return x&(-x) ; } 圖中~i是對i按位取反，由于機器中數字是用補碼存的，是以- i =(~i)+1
x&(-x) 自然就可以求出lowbit(x) 了。
六、時間複雜度與空間複雜度
令 k1=x+lowbit(x) . k2=x-lowbit(x). 易得lowbit(k1) > x 且 lowbit(k2) > x.
即k1和k2都至少比 x 高一層，x的層數越來越高，而總層數為 floor( log2(n) )+1 于是Add和Sum操作都是O(log2(n))的。
跟線段樹比較的話，線段樹的修改操作幾乎要更改 floor( log2(n) )+1 個節點，
而樹狀數組最多才改 floor( log2(n) )+1 節點，最少隻用改1個節點（比如n=11的時候更改A[8]）
樹狀數組的優點第一是快，第二是它真真正正隻用了1倍空間，都不需要向上擴充到2的某個次方。
線段樹是要先把n向上擴充到最小的某個2的次方，然後再乘個2（一般為了省事就直接開4*n的數組了）。
《統計的力量》裡面提到的用非遞歸線段樹省掉一半空間（省掉所有右子樹）也可以用一倍空間的說法其實不是很對，
就算非遞歸也是需要向上擴充到最小的某個2的次方的。
省掉一半空間的非遞歸線段樹需要的數組元素個數為：
而它的範圍見右邊公式：
是以是需要向上擴充一定的空間的，n個數組元素是不夠用的。
為了友善，直接擴充到大于n的最小2的次方就行了(省了一半空間，但也隻能求字首和，不能直接求區間和了)。
附上省掉一半空間的非遞歸線段樹代碼：
int N;
int A[maxn],sum[maxn];
int Sum(int x){//前x項的和
int ANS=0;
for(int t=x+N;t^1;t>>=1){
if(t&1) ANS+=sum[t/2];//在省掉空間之前是要通路節點t^1的，由于t^1一定為偶數，是以用(t^1)/2 = t/2來儲存原來t^1的節點内容</span>
}//由于這樣做，所有奇數節點都不會被通路，是以奇數節點全部不存了（省掉一半空間）。</span>
return ANS;
}
void Add(int x,int c){
for(int t=x+N-1;t^1;t>>=1){
if(~t&1) sum[t/2]+=c;
}
}
void Build(int n){//n為數組元素個數，将數組存入A中，然後調用Build然後就可以正常的使用Add和Sum函數了
N=1;while(N <= n) N <<= 1;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;++i) Add(i,A[i]);
} 再來說說樹狀數組的建樹效率：
按之前的圖檔那樣每次篩選出偶數來建樹的的操作次數為
而直接使用n次Add函數的操作次數為：
，這個式子好像沒辦法再化簡了。
但它每一項約等于n/2,共
個非零項，是以總複雜度是
七、樹狀數組其它用法
第一種：區間修改，點查詢
思想其實是化區間修改為點修改，不使用C[i]數組了。
增加B數組。假設B[i]=t , 則表示對區間A[i],A[i+1],...,A[n]都增加了t.
那麼，把區間[L,R]的數都加上X的操作就變成了兩個點修改：B[L]+=X 和 B[R+1]-=X;//這裡是簡寫，還需要更新它們的父節點
然後查詢點X的時候，要求B[1]+B[2]+...+B[X]的和再加上A[X]，因為這些點上的修改都會影響到X.
第二種：區間修改，區間查詢
這裡就用到一點數學了，用a[i]表示A[i]-A[i-1]（假設A[0]=0）
用S[i]表示a[1]+a[2]+...+a[i] ,用 P[i] 表示 a[1]+2*a[2]+3*a[3]+...+i*a[i]
則字首和的字首和 SS[x]=S[1]+S[2]+S[3]+...+S[x]=x*a[1]+(x-1)*a[2] +...+2*a[x-1] + a[x] = (x+1)S[x]- P[x]
于是隻要對差分數列維護S[i]和P[i]兩個性質就好了。
S[i]維護原數組為a[i]的字首和（=A[i]），P[i]維護原數組為 i*a[i]的字首和
區間修改的話，A[L]-A[L-1]多了X。A[R+1]-A[R] 少了X。即 a[L]+=X. a[R+1]-=X; 兩個點修改
每個點都要修改S和P兩個數組。
代碼如下：
#define LL long long
#define maxn 100001
int N,Q;
LL A[maxn];
LL P[maxn],S[maxn];
void AddP(LL x,LL v){
if(!x) return;
while(x <=N){
P[x]+=v;
x+=x&-x;
}
}
void AddS(LL x,LL v){
if(!x) return;
while(x <=N){
S[x]+=v;
x+=x&-x;
}
}
LL SumP(LL x){
LL ans=0;
while(x>0){
ans+=P[x];
x-=x&-x;
}
return ans;
}
LL SumS(LL x){
LL ans=0;
while(x>0){
ans+=S[x];
x-=x&-x;
}
return ans;
}
void INC(LL L,LL R,LL C){//區間[L,R]都加C
AddS(L,C);AddS(R+1,-C);
AddP(L,L*C);AddP(R+1,-(R+1)*C);
}
LL QUE(LL a){//詢問字首和
return (a+1)*SumS(a)-SumP(a);
} 第三種：二維樹狀數組
二維樹狀數組就是可以在
的時間内求一個矩陣的一個矩形區域的和，和改變矩陣中一點的值。
了解了一維的樹狀數組的話，仔細想想就知道二維的情況了。
int n;
int A[1002][1002];
void Add(int x,int y,int K){//A[x][y]增加K
while(x <= n){
int yy=y;
while(yy <= n){
A[x][yy]+=K;
yy+=yy&-yy;
}
x+=x&-x;
}
}
int Sum(int x,int y){//求矩陣i<=x,j<=y的所有元素和
int ANS=0;
while(x > 0){
int yy=y;
while(yy > 0){
ANS+=A[x][yy];
yy-=yy&-yy;
}
x-=x&-x;
}
return ANS;
} 八、結語
以前學了線段樹，聽說樹狀數組功能比線段樹少，就一直沒有學，直到去查 動态區間第k大的題解的時候，滿眼的 樹狀數組套主席樹
于是決定學一下樹狀數組，然後發現樹狀數組還是很好用的，代碼簡單而且效率高，隻用開n的空間不需要向上擴充。
效率上非遞歸線段樹其實也差不多，但是非遞歸線段樹的要進行複雜的下标變換，每次寫都要想半天，
還是樹狀數組寫起來簡潔一些，是以能寫樹狀數組的就可以避免寫複雜的線段樹了。