夜深人靜寫算法（三） - 樹狀數組

圖二-1-1

如圖二-1-1，其中A為普通數組，C為樹狀數組（C在物理空間上和A一樣都是連續存儲的）。樹狀數組的第4個元素C4的父結點為C8 (4的二進制表示為”100″，所以k=2，那么4 + 2^2 = 8)，C6和C7同理。C2和C3的父結點為C4，同樣也是可以用上面的關系得出的，那么從定義出發，奇數下標一定是葉子結點。

2、結點的含義

然后我們來看樹狀數組上的結點Ci具體表示什么，這時候就需要利用樹的遞歸性質了。我們定義Ci的值為它的所有子結點的值 和 Ai 的總和，之前提到當i為奇數時Ci一定為葉子結點，所以有Ci = Ai ( i為奇數 )。從圖中可以得出：
C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
建議直接看C8，因為它最具代表性。

我們從中可以發現，其實Ci還有一種更加普適的定義，它表示的其實是一段原數組A的連續區間和。根據定義，右區間是很明顯的，一定是i，即Ci表示的區間的最后一個元素一定是Ai，那么接下來就是要求Ci表示的第一個元素是什么。從圖上可以很容易的清楚，其實就是順著Ci的最左兒子一直找直到找到葉子結點，那個葉子結點就是Ci表示區間的第一個元素。

更加具體的，如果i的二進制表示為 ABCDE1000，那么它最左邊的兒子就是 ABCDE0100，這一步是通過結點父子關系的定義進行逆推得到，并且這條路徑可以表示如下：
ABCDE1000 => ABCDE0100 => ABCDE0010 => ABCDE0001

這時候，ABCDE0001已經是葉子結點了，所以它就是Ci能夠表示的第一個元素的下標，那么我們發現，如果用k來表示i的二進制末尾0的個數，Ci能夠表示的A數組的區間的元素個數為2^k，又因為區間和的最后一個數一定是Ai，所以有如下公式：
Ci = sum{ A[j] | i – 2^k+ 1 <= j <= i } （幫助理解：將j的兩個端點相減+1 等于2^k）

3、求和操作

明白了Ci的含義后，我們需要通過它來求sum{ A[j] | 1 <= j <= i }，也就是之前提到的sum(i)函數。為了簡化問題，用一個函數lowbit(i)來表示2^k(k等于i的二進制表示中末尾0的個數)。那么：
sum(i) = sum{ A[j] | 1 <= j <= i } = A[1] + A[2] + … + A[i]
= A[1] + A[2] + A[i-2^k] + A[i-2^k+1] + … + A[i]
= A[1] + A[2] + A[i-2^k] + C[i]
= sum(i - 2^k) + C[i]
= sum( i – lowbit(i) ) + C[i]

由于C[i]已知，所以sum(i)可以通過遞歸求解，遞歸出口為當i = 0時，返回0。sum(i)函數的函數主體只需要一行代碼：

int sum(int x){
     return x ? C[x]+ sum( x - lowbit(x)):0;
}

觀察 i – lowbit(i)，其實就是將i的二進制表示的最后一個1去掉，最多只有log(i)個1，所以求sum(n)的最壞時間復雜度為O(logn)。由于遞歸的時候常數開銷比較大，所以一般寫成迭代的形式更好。寫成迭代代碼如下：

int sum(int x){
        int s =0;
        for(int i = x; i ; i -= lowbit(i)){
            <strong>s += c[i][j];</strong>
        }
        return s;    
    }

4、更新操作

更新操作就是之前提到的add(i, 1) 和 add(i, -1)，更加具體得，可以推廣到add(i, v)，表示的其實就是 A[i] = A[i] + v。但是我們不能在原數組A上操作，而是要像求和操作一樣，在樹狀數組C上進行操作。

那么其實就是求在Ai改變的時候會影響哪些Ci，看圖二-1-1的樹形結構就一目了然了，Ai的改變只會影響Ci及其祖先結點，即A5的改變影響的是C5、C6、C8；而A1的改變影響的是C1、C2、C4、C8。

也就是每次add(i, v)，我們只要更新Ci以及它的祖先結點，之前已經討論過兩個結點父子關系是如何建立的，所以給定一個x，一定能夠在最多log(n) (這里的n是之前提到的值域) 次內更新完所有x的祖先結點，add(i, v)的主體代碼（去除邊界判斷）也只有一行代碼：

void add(int x,int v){
     if(x <= n){
         C[x]+= v, add( x + lowbit(i), v );
     }
}

和求和操作類似，遞歸的時候常數開銷比較大，所以一般寫成迭代的形式更好。寫成迭代形式的代碼如下：

void add(int x,int v){
    for(int i = x; i <= n; i += lowbit(i)){
        C[i] += v;
    }
}

5、lowbit函數O(1)實現

上文提到的兩個函數sum(x)和add(x, v)都是用遞歸實現的，并且都用到了一個函數叫lowbit(x)，表示的是，其中k為x的二進制表示末尾0的個數，那么最簡單的實現辦法就是通過位運算的右移，循環判斷最后一位是0還是1，從而統計末尾0的個數，一旦發現1后統計完畢，計數器保存的值就是k，當然這樣的做法總的復雜度為O( logn )，一個32位的整數最多可能進行31次判斷（這里討論整數的情況，所以符號位不算）。這里介紹一種O(1)的方法計算2^k的方法。

正數：正數的補碼即其二進制表示；例如一個8位二進制的整數+5，它的補碼就是 00000101 （標紅的是符號位，0表示”正”，1表示“負”）

負數：負數的補碼即將其整數對應的二進制表示所有位取反(包括符號位)后+1；例如一個8位二進制的整數-5，它的二進制表示是00000101，取反后為11111010，再+1就是11111011，這就是它的補碼了。

下面的等式可以幫助理解補碼在計算機中是如何工作的：
+5 + (-5) = 00000101 + 11111011 = 1 00000000 (溢出了!!!) = 0這里的加法沒有將數值位和符號位分開，而是統一作為二進制位進行計算，由于表示的是8進制的整數，所以多出的那個最高位的1會直接舍去，使得結果變成了0，而實際的十進制計算結果也是0，正確。

補碼復習完畢，那么來看下下面這個表達式的含義：x & (-x) (其中 x >= 0)

首先進行&運算，我們需要將x和-x都轉化成補碼，然后再看&之后會發生什么，我們假設 x 的二進制表示的末尾是連續的 k 個 0，令x的二進制表示為 X₀X₁X₂…X_n-2X_{n-1, 則} {X_i = 0 | n-k <= i < n}， 這里的X₀表示符號位。

x的補碼就是由三部分組成：(0)(X₁X₂…X_n-k-1)(k個0) 其中X_n-k-1為1，因為末尾是k個0，如果它為0，那就變成k+1個0了。

-x的補碼也是由三部分組成：(1)(Y₁Y₂…Y_n-k-1)(k個0) 其中Y_{n-k-1為1，其它的}X_i和Y_i相加為1，想想補碼是怎么計算的就明白了。

那么 x & (-x) 也就顯而易見了，由兩部分組成 (1)(k個0)，表示成十進制為 2^k 啦。由于&的優先級低于-，所以代碼可以這樣寫：

int lowbit(int x) {
     return x & -x;
}

6、小結

至此，樹狀數組的基礎內容就到此結束了，三個函數就詮釋了樹狀數組的所有內容，并且都只需要一行代碼實現，單次操作的時間復雜度為O( log(n) )，空間復雜度為O(n)，所以它是一種性價比非常高的輕量級數據結構。

樹狀數組解決的基本問題是 單點更新，成端求和。上文中的sum(x)求的是[1, x]的和，如果需要求[x, y]的和，只需要求兩次sum函數，然后相減得到，即sum(y) – sum(x-1)。

下面一節會通過一些例子來具體闡述樹狀數組的應用場景。

三、樹狀數組的經典模型

1、PUIQ模型

【例題1】一個長度為n(n <= 500000)的元素序列，一開始都為0，現給出三種操作：
1. add x v : 給第x個元素的值加上v； ( a[x] += v )
2. sub x v : 給第x個元素的值減去v； ( a[x] -= v )
3. sum x y： 詢問第x到第y個元素的和； ( print sum{ a[i] | x <= i <= y } )

這是樹狀數組最基礎的模型，1和2的操作就是對應的單點更新，3的操作就對應了成端求和。

具體得，1和2只要分別調用add(x, v)和add(x, -v), 而3則是輸出sum(y) – sum(x-1)的值。

我把這類問題叫做PUIQ模型(Point Update Interval Query 點更新，段求和)。

2、IUPQ模型

【例題2】一個長度為n(n <= 500000)的元素序列，一開始都為0，現給出兩種操作：
1. add x y v : 給第x個元素到第y個元素的值都加上v； ( a[i] += v, 其中 x <= i <= y )
2. get x： 詢問第x個元素的值； ( print a[x] )

這類問題對樹狀數組稍微進行了一個轉化，但是還是可以用add和sum這兩個函數來解決，對于操作1我們只需要執行兩個操作，即add(x, v)和add(y+1, -v)；而操作2則是輸出sum(x)的值。

這樣就把區間更新轉化成了單點更新，單點求值轉化成了區間求和。

我把這類問題叫做IUPQ模型(Interval Update Point Query 段更新，點求值)。

3、逆序模型

【例題3】給定一個長度為n(n <= 500000)的排列a[i]，求它的逆序對對數。1 5 2 4 3 的逆序對為(5,2)(5,3)(5,4)(4,3)，所以答案為4。

樸素算法，枚舉任意兩個數，判斷他們的大小關系進行統計，時間復雜度O(n²)。不推薦！來看一個給定n個元素的排列 X₀ X₁ X₂ … X_n-2 X_n-1,對于某個 X_i 元素，如果想知道以它為”首”的逆序對的對數( 形如(X_iX_j) 的逆序對)，就是需要知道 X_i+1 … X_n-2 X_n-1 這個子序列中小于X_i 的元素的個數。

那么我們只需要對這個排列從后往前枚舉，每次枚舉到 X_i 元素時，執行cnt += sum(X_i-1)，然后再執行add(X_i, 1)，n個元素枚舉完畢，得到的cnt值就是我們要求的逆序數了。總的時間復雜度O(nlogn)。

這個模型和之前的區別在于它不是將原數組的下標作為樹狀數組的下標，而是將元素本身作為樹狀數組的下標。逆序模型作為樹狀數組的一個經典思想有著非常廣泛的應用。

【例題4】給定N(N <= 100000)個區間，定義兩個區間(Si, Ei)和(Sj, Ej)的’>’如下：
如果Si <= Sj and Ej <= Ei and Ei – Si > Ej – Sj,則(Si, Ei) > (Sj, Ej)，現在要求每個區間有多少區間’>’它。將上述三個關系式化簡，可以得到 區間i > 區間j 的條件是：區間i 完全覆蓋 區間j，并且兩者不相等。

void add(int x,int y,int v){
    for(int i = x; i <= n; i += lowbit(i)){
        for(int j = y; j <= n; j += lowbit(j)){
            c[i][j]+= v;
        }
    }
}

int sum(int x,int y){
     int s =0;
     for(int i = x; i ; i -= lowbit(i)){
         for(int j = y; j ; j -= lowbit(j)){
             s += c[i][j];
         }
     }
     return s;
}