ACM___________________________

簡單介紹下 樹狀數(shù)組 :

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

來觀察一下這個圖：

令這棵樹的結(jié)點(diǎn)編號為C1，C2……Cn。令每個結(jié)點(diǎn)的值為這棵樹的值的總和，那么容易發(fā)現(xiàn)：

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

這里有一個有趣的性質(zhì)，下午推了一下發(fā)現(xiàn)：

設(shè)節(jié)點(diǎn)編號為x，那么這個節(jié)點(diǎn)管轄的區(qū)間為2^k（其中k為x二進(jìn)制末尾0的個數(shù)）個元素。因為這個區(qū)間最后一個元素必然為Ax，所以很明顯：

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

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

int lowbit(int x){

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

}

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

step1:　令sum = 0，轉(zhuǎn)第二步；

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

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

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

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

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

step1: 當(dāng)i > n時，算法結(jié)束，否則轉(zhuǎn)第二步；

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

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

//修改過程必須滿足減法規(guī)則！

所以整個程序如下：

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 ); 

                 }