問題提出：已知數(shù)組a[],元素個數(shù)為n,現(xiàn)在更改a中的元素,要求得新的a數(shù)組中i到j(luò)區(qū)間內(nèi)的和(1<=i<=j<=n).

思考：對于這個問題,我們可以暴力地來解決,從a[i]一直累加到a[j],最壞的情況下復(fù)雜度為O(n),對于m次change&querry,合起來的復(fù)雜度為O(m*n),在n或m很大的情況下,這樣的復(fù)雜度是讓人無法忍受的.另外,如果沒有元素的變更,我們完全可以存儲sum[1,k](k=1,2,……),然后對任意給定的查找區(qū)間[i,j],都可以方便的用ans=sum[1,j]-sum[1,i-1],當(dāng)然這只是沒有元素改變的情況下的比較優(yōu)化的解法.那么對于有元素變更的問題是否有更高效的方法呢?(廢話!沒有我還寫啥?!)可以想一下,每次更改的元素是比較少的,有時候甚至每次只改變一個元素,但是在用暴力方法求區(qū)間和的時候,卻對區(qū)間內(nèi)所有的元素都累加了一遍,這樣其實造成了許多無謂的運(yùn)算.這時候也許會想到如果能把一些結(jié)果存起來會不會減少很多運(yùn)算?答案是肯定的,但問題是怎么存,存什么?如果存任意區(qū)間的話,n比較大的時候不但內(nèi)存吃不消,而且存儲的量太大,不易更改,反而得不償失;那么也許可以考慮存儲特定的一些區(qū)間(比如說線段樹,其實現(xiàn)在討論的問題用線段樹完全可以解,以后再詳細(xì)寫線段樹).那么現(xiàn)在重新回過頭來,看下這個問題,我們已經(jīng)確定了要存儲一些特定區(qū)間sum的想法,接下來我們要解決的無非是兩個問題:1、減少更改元素后對這些區(qū)間里的sum值的更改時間.2、減少查找的時間.

好了廢話了這么半天,無非是想讓自己以及看到的人明白為什么要用樹狀數(shù)組.

接下來正式入題.

首先我們可以借鑒元素不變更問題的優(yōu)化方法,先得到前i-1項之和and前j項之和,以s[i]表示前i項之和,那么sum[i,j]=s[j]-s[i-1].那么現(xiàn)在的問題已經(jīng)轉(zhuǎn)化為求前i項之和了.另外,我們已經(jīng)確定要存儲一些特定區(qū)間的和,現(xiàn)在就要來揭示這些特定的區(qū)間究竟指什么.

在文字說明之前先引入一個非常經(jīng)典的,在網(wǎng)上找到的樹狀數(shù)組文章里幾乎都要出現(xiàn)的一個圖片

從圖中不難發(fā)現(xiàn),c[k]存儲的實際上是從k開始向前數(shù)k的二進(jìn)制表示中右邊第一個1所代表的數(shù)字個元素的和(這么說可能有點拗口,令lowbit為k的二進(jìn)制表示中右邊第一個1所代表的數(shù)字,然后c[k]里存的就是從a[k]開始向前數(shù)lowbit個元素之和)這么存有什么好處呢?無論是樹狀數(shù)組還是線段樹,都用到了分塊的思想,而樹狀數(shù)組采用這樣的存儲結(jié)構(gòu)我想最主要的還是這樣方便計算,我們可以用位運(yùn)算輕松地算出lowbit.分析一下這樣做的復(fù)雜度:對于更改元素來說,如果第i個元素被修改了,因為我們最終還是要求和,所以可以直接在c數(shù)組里面進(jìn)行相應(yīng)的更改,如圖中的例子,假設(shè)更改的元素是a[2],那么它影響到得c數(shù)組中的元素只有c[2],c[4],c[8],我們只需一層一層往上修改就可以了,這個過程的最壞的復(fù)雜度也不過O(logN);對于查找來說,如查找s[k],只需查找k的二進(jìn)制表示中1的個數(shù)次就能得到最終結(jié)果,比如查找s[7],7的二進(jìn)制表示中有3個1,也就是要查找3次,到底是不是呢,我們來看上圖,s[7]=c[7]+c[6]+c[4],可能你還不知道怎么實現(xiàn)這個過程.

還以7為例,二進(jìn)制為0111,右邊第一個1出現(xiàn)在第0位上,也就是說要從a[7]開始向前數(shù)1個元素(只有a[7]),即c[7];

然后將這個1舍掉,得到6,二進(jìn)制表示為0110,右邊第一個1出現(xiàn)在第1位上,也就是說要從a[6]開始向前數(shù)2個元素(a[6],a[5]),即c[6];

然后舍掉用過的1,得到4,二進(jìn)制表示為0100,右邊第一個1出現(xiàn)在第2位上,也就是說要從a[4]開始向前數(shù)4個元素(a[4],a[3],a[2],a[1]),即c[4].

代碼實現(xiàn):

Code
int lowbit(int x)//計算lowbit
{
    return x&(-x);
}
void add(int i,int val)//將第i個元素更改為val
{
    while(i<=n)
    {
        c[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i)//求前i項和
{
    int s=0;
    while(i>0)
    {
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

http://www.cnblogs.com/yykkciwei/archive/2009/05/08/1452889.html