樹狀數組是一個優美小巧的數據結構，在很多時候可以代替線段樹。一句話概括就是，凡是樹狀數組可以解決的問題，線段樹都可以解決，反過來線段樹可以解決的問題，樹狀數組不一定能解決。

樹狀數組英文名稱爲Binary Index Tree，直譯過來就是二進制索引樹，我覺得二進制索引樹更能說明其本質。樹狀數組的本質就是一種通過二進制位來維護一個序列前i和的數據結構。

對於維護的序列A，定義C[i]=A[j+1]+...+A[i]，其中j爲i的二進制表示中把最右邊的1換成0的值。j的值可以通過lowbit求出，即i-lowbit(i)。

lowbit(a)爲2^(a的二進制表示末尾0的個數)。可以用下面式子求出

lowbit(a)=a&(~a+1)

或者根據補碼的性質簡化爲

lowbit(a)=a&(-a)

修改方式如下

    void modify(int p,int delta)
    {
        while (p<=N)
        {
            C[p]+=delta;
            p+=lowbit(p);
        }
    }

求前綴和如下

    int sum(int p)
    {
        int rs=0;
        while (p)
        {
            rs+=C[p];
            p-=lowbit(p);
        }
        return rs;
    }

BYVoid 原創講解，轉載請註明。