ACM___________________________

簡單介紹下 樹狀數組 :

     　　 樹狀數組是一個查詢和修改復雜度都為log(n)的數據結構，假設數組a[1...n]，那么查詢a[1] + …… + a[i]　的時間是log級別的，而且是一個在線的數據結構，支持隨時修改某個元素的值，復雜度也為log級別。

來觀察一下這個圖：

令這棵樹的結點編號為C1，C2……Cn。令每個結點的值為這棵樹的值的總和，那么容易發現：

C1 = A1

C2 = A1 + A2

C3 = A3

C4 = A1 + A2 + A3 + A4

C5 = A5

C6 = A5 + A6

C7 = A7

C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

……

C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16

這里有一個有趣的性質，下午推了一下發現：

設節點編號為x，那么這個節點管轄的區間為2^k（其中k為x二進制末尾0的個數）個元素。因為這個區間最后一個元素必然為Ax，所以很明顯：

Cn = A(n – 2^k + 1) + …… + An

算這個2^k有一個快捷的辦法，定義一個函數如下即可：

int lowbit(int x){

return x & (x ^ (x – 1));

}

當想要查詢一個SUM(n)時，可以依據如下算法即可：

step1:　令sum = 0，轉第二步；

step2:　假如n <= 0，算法結束，返回sum值，否則sum = sum + Cn，轉第三步；

step3:  令n = n – lowbit(n)，轉第二步。

可以看出，這個算法就是將這一個個區間的和全部加起來，為什么是效率是log(n)的呢？以下給出證明：

n = n – lowbit(n)這一步實際上等價于將n的二進制的最后一個1減去。而n的二進制里最多有log(n)個1，所以查詢效率是log(n)的。

那么修改呢，修改一個節點，必須修改其所有祖先，最壞情況下為修改第一個元素，最多有log(n)的祖先。所以修改算法如下（給某個結點i加上x）：

step1: 當i > n時，算法結束，否則轉第二步；

step2: Ci = Ci + x， i = i + lowbit(i)轉第一步。

i = i +lowbit(i)這個過程實際上也只是一個把末尾1補為0的過程。

//修改過程必須滿足減法規則！

所以整個程序如下：

const int MAX = 50000;

#define lowbit(x) ((x)&(-x))

int com[ MAX + 1 ],N,T;

void modify ( int pos, int val ){

     while ( pos <= N ){

            com[pos] += val;

            pos = pos + lowbit(pos);  

     } 

}

int quy ( int x ){

    int sum = 0;

    while ( x > 0 ){

           sum = sum + com[x];

           x = x - lowbit(x);

    } 

    return sum;

}

初始化 :  　　 for ( int i = 1; i <= N; ++ i ){

                       scanf ( "%d",&x );

                       modify ( i, x ); 

                 }