【引言】

          在解題過程中，我們有時(shí)需要維護(hù)一個(gè)數(shù)組的前綴和S[i]=A[1]+A[2]+...+A[i]。

          但是不難發(fā)現(xiàn)，如果我們修改了任意一個(gè)A[i],S[i]、S[i+1]...S[n]都會(huì)發(fā)生變化。

          可以說，每次修改A[i]后，調(diào)整前綴和S[]在最壞情況下會(huì)需要O(n)的時(shí)間。

          當(dāng)n非常大時(shí)，程序會(huì)運(yùn)行得非常緩慢。

          因此，這里我們引入“樹狀數(shù)組”，它的修改與求和都是O(logn)的，效率非常高。

【理論】

          為了對(duì)樹狀數(shù)組有個(gè)形 象的認(rèn)識(shí)，我們先看下面這張圖。

          這里，C[i]表示A[i-2^k+1]到A[i]的和，而k則是i在二進(jìn)制時(shí)末尾0的個(gè)數(shù)，

          或者說是i用2的冪方和表示時(shí)的最小指數(shù)。

         （ 當(dāng)然，利用位運(yùn)算，我們可以直接計(jì)算出2^k=i&(i^(i-1)) ）

          同時(shí)，我們也不難發(fā)現(xiàn)，這個(gè)k就是該節(jié)點(diǎn)在樹中的高度，因而這個(gè)樹的高度不會(huì)超過logn。

          所以,當(dāng)我們修改A[i]的值時(shí)，可以從C[i]往根節(jié)點(diǎn)一路上溯，調(diào)整這條路上的所有C[]即可，

          這個(gè)操作的復(fù)雜度在最壞情況下就是樹的高度即O(logn)。  

          另外，對(duì)于求數(shù)列的前n項(xiàng)和，只需找到n以前的所有最大子樹，把其根節(jié)點(diǎn)的C加起來即可。

          不難發(fā)現(xiàn)，這些子樹的數(shù)目是n在二進(jìn)制時(shí)1的個(gè)數(shù)，或者說是把n展開成2的冪方和時(shí)的項(xiàng)數(shù),

          因此，求和操作的復(fù)雜度也是O(logn)。

          接著，我們考察這兩種操作下標(biāo)變化的規(guī)律：

          首先看修改操作：

          已知下標(biāo)i，求其父節(jié)點(diǎn)的下標(biāo)。
          我們可以考慮對(duì)樹從邏輯上轉(zhuǎn)化：

         如圖，我們將子樹向右對(duì)稱翻折，虛擬出一些空白結(jié)點(diǎn)（圖中白色），將原樹轉(zhuǎn)化成完全二叉樹。

         有圖可知，對(duì)于節(jié)點(diǎn)i，其父節(jié)點(diǎn)的下標(biāo)與翻折出的空白節(jié)點(diǎn)下標(biāo)相同。

         因而父節(jié)點(diǎn)下標(biāo) p=i+2^k  (2^k是i用2的冪方和展開式中的最小冪，即i為根節(jié)點(diǎn)子樹的規(guī)模)

         即  p = i + i&(i^(i-1)) 。

         接著對(duì)于求和操作：

         因?yàn)槊靠米訕涓采w的范圍都是2的冪，所以我們要求子樹i的前一棵樹，只需讓i減去2的最小冪即可。

         即  p = i - i&(i^(i-1)) 。

         至此，我們已經(jīng)比較詳細(xì)的分析了樹狀數(shù)組的復(fù)雜度和原理。

         在最后，我們將給出一些樹狀數(shù)組的實(shí)現(xiàn)代碼，希望讀者能夠仔細(xì)體會(huì)其中的細(xì)節(jié)。

【代碼】

 求最小冪2^k:

int LowBit(int n)
{
    return n & (-n);
}

int Sum(int nPos)
{
    int nSum = 0;
    while (nPos > 0)
    {
        nSum += C[nPos];
        nPos -= LowBit(nPos);
    }

    return nSum;
}

void Modify(int nPos, int delta)
{
    while (nPos <= DATA_SIZE)
    {
        C[nPos] += delta;
        nPos += LowBit(nPos);
    }
}

#include <iostream.h>
#include <stdlib.h> 
#include <malloc.h>
#include <windows.h>

#define DATA_SIZE 10000000

int A[DATA_SIZE];
int C[DATA_SIZE];

int LowBit(int n)
{
    return n & (-n);
}


// Binary Indexed tree
int Sum1(int nPos)
{
    int nSum = 0;
    while (nPos > 0)
    {
        nSum += C[nPos];
        nPos -= LowBit(nPos);
    }

    return nSum;
}

void Modify(int nPos, int delta)
{
    while (nPos <= DATA_SIZE)
    {
        C[nPos] += delta;
        nPos += LowBit(nPos);
    }
}

// Common Plus
int Sum2(int nPos)
{
    int nSum = 0;
    for ( int i=1; i<DATA_SIZE; i++ )
    {
        nSum += A[i];
    }

    return nSum;
}


main()
{

    DWORD dwBegin,dwEnd;
    dwBegin = dwEnd = GetTickCount();

    int nIndexChanged = 10;
    int nData = 100;

    A[nIndexChanged] = nData;
    Modify(nIndexChanged,nData);

    int nSum = Sum1(DATA_SIZE-1);
    cout<<nSum<<endl;
    dwEnd = GetTickCount();
    int nDiff = dwEnd-dwBegin;
    cout<<"Time1:"<<dwEnd-dwBegin<<endl;
    cout<<"---------------------"<<endl;

    dwBegin = dwEnd = GetTickCount();
    nSum = Sum2(DATA_SIZE-1);
    cout<<nSum<<endl;
    dwEnd = GetTickCount();
    nDiff = dwEnd-dwBegin;
    cout<<"Time2:"<<nDiff<<endl;
    cout<<"---------------------"<<endl;
    
    return 0;
}