資料結構 —— 樹狀數組

【概述】

樹狀數組又稱二叉索引樹，常用于高效計算數列的字首和、區間和，其查詢、修改的時間複雜度為 log(n)，空間複雜度為 O(n)

樹狀數組通過将線性結構轉化成樹狀結構，進而進行跳躍式掃描。

優點：

1. 代碼短小，實作簡單
2. 容易擴充到高緯度的資料

缺點：

1. 隻能用于求和，不能求最值
2. 不能動态插入
3. 資料多時，空間壓力大

【原理】

1.對于一個普通的二叉樹，葉子結點代表 A 數組的 A[1]~A[8]

2.将其進行簡單的變形

3.然後定義每一列的頂端結點 C[] 數組，令 C[i] 代表子樹的葉結點的權值之和

如上圖，可知：

• C[1]=A[1]
• C[2]=A[1]+A[2]
• C[3]=A[3]
• C[4]=A[1]+A[2]+A[3]+A[4]
• C[5]=A[5]
• C[6]=A[5]+A[6]
• C[7]=A[7]
• C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]

4.将 C[] 數組的結點序号轉化為二進制

如上圖，有：

• 1=(001)，C[1]=A[1]
• 2=(010)，C[2]=A[1]+A[2]
• 3=(011)，C[3]=A[3]
• 4=(100)，C[4]=A[1]+A[2]+A[3]+A[4]
• 5=(101)，C[5]=A[5]
• 6=(110)，C[6]=A[5]+A[6]
• 7=(111)，C[7]=A[7]
• 8=(1000)，C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]

可以發現  C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i]，其中，k 為 i 的二進制中從最低位到高位連續零的長度，例如：i=8 時，k=3

要注意的是，樹狀數組隻能計算 A[1] 開始的和，A[0] 這個元素是不能用的

【具體實作】

1.lowbit(x)

lowbit(x) 就是取出 x 的最低位 1，換言之 lowbit(x)=2^k，k 為 i 的二進制中從最低位到高位連續零的長度

那麼有：C[i] = A[i-2^k+1]+A[i-2^k+2]+......A[i] = A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+......A[i]

對于一個數 x，想求其 lowbit，可借助 x 的負數 -x，進行與運算

例如：

t = 6(0110)，此時 k=1

-t = -6 = (1001+1) = (1010)

t&(-t) = (0010) = 2=2^1

//傳回i的二進制最右邊1的值
int lowbit(int t){
    return t&(-t);
}
           

2.區間查詢

利用 C[] 數組，求 A 數組中前 i 項的和 sum[i]

• 以 i=7 為例：sum[7] = A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]

  其中：C[4] = A[1]+A[2]+A[3]+A[4]，C[6] = A[5]+A[6]，C[7]=A[7]

  那麼：sum[7] = C[4]+C[6]+C[7]

  改寫為二進制：sum[(111)] = C[(100)]+C[(110)]+C[(111)]

• 以 i=5 為例：sum[5] = A[1]+A[2]+A[3]+A[4]+A[5]

  其中：C[4] = A[1]+A[2]+A[3]+A[4]，C[5]=A[5]

  那麼：sum[5] = C[4]+C[5]

  改寫為二進制：sum[(101)] = C[(100)]+C[(101)];

仔細觀察最後改寫為二進制的數組，可以發現，樹狀數組根本上來說就是二進制的應用。

對于要求的前 x 項的和，每次加上 C[x]，然後令 x=x-lowbit(x)，如此循環往複，直到 x-lowbit(x)=0 為止

• 以 i=7 進行示範

  7(111)，ans+=C[7]

  7-lowbit(7) = 7-lowbit(111) = 7-1 = 6(110)，ans+=C[6]

  6-lowbit(6) = 6-lowbit(110) = 6-2 = 4(100)，ans+=C[4]

  4-lowbit(4) = 4-lowbit(100) = 4-4 = 0(000) 

  故有：sum[7] = C[4]+C[6]+C[7]

• 以 i=5 進行示範

  5(101)，ans+=C[5]

  5-lowbit(5) = 5-lowbit(101) = 5-1 = 4(100)，ans+=C[4]

  4-lowbit(4) = 4-lowbit(100) = 4-4 = 0(000) 

  故有：sum[5]=C[5]+C[4]

//傳回A[1]+...A[i]的和
int getSum(int i){
    int res=0;
    while(i>0){
        res+=C[i];
        i-=lowbit(i);
    }
    return res;
}
           

3.單點更新

當修改 A[] 數組中的某一個值時，需要對 C[] 數組進行更新

如圖：

當更新 A[1] 時，需要向上更新 C[1]、C[2]、C[4]、C[8]， 将 C[1]、C[2]、C[4]、C[8] 改寫為二進制：C[(001)]、C[(010)]、C[(100)]、C[(1000)]

則：

1(001)，C[1]+=A[1]

1+lowbit(1) = 1+lowbit(1) = 1+1 = 2(010)，C[2]+=A[1]

2+lowbit(2) = 2+lowbit(010) = 2+2 = 4(100)，C[4]+=A[1]

4+lowbit(4) = 4+lowbit(100) = 4+4 = 8(1000)，C[8]+=A[1]

可以發現：更新過程是查詢過程的逆過程。

//令A[i]+=val
void add(int i,int val){
    while(i<=n){
        C[i]+=val;
        i+=lowbit(i);
    }
}
           

【模版】

const int N=10000+5;//最大元素個數
int n;//元素個數
int c[N];//c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]
 
//傳回i的二進制最右邊1的值
int lowbit(int i){
    return i&(-i);
}
 
//傳回A[1]+...A[i]的和
int getSum(int i){
    int res=0;
    while(i>0){
        res+=c[i];
        i-=lowbit(i);
    }
    return res;
}
 
//令A[i]+=val
void add(int i,int val){
    while(i<=n){
        c[i]+=val;
        i+=lowbit(i);
    }
}
           

【例題】