ACM___________________________

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

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

來(lái)觀察一下這個(gè)圖：

令這棵樹(shù)的結(jié)點(diǎn)編號(hào)為C1，C2……Cn。令每個(gè)結(jié)點(diǎn)的值為這棵樹(shù)的值的總和，那么容易發(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

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

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

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

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

int lowbit(int x){

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

}

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

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

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

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

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

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

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

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

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

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

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

所以整個(gè)程序如下：

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

                 }