【數(shù)據(jù)結(jié)構(gòu)】樹狀數(shù)組

講到了線段樹，那就順便講講樹狀數(shù)組吧。

問題：

• 一個(gè)固定大小 n 的有限數(shù)組 x
• action 1 : 可以隨時(shí)更新某個(gè)節(jié)點(diǎn) i 的元素
• action 2 : 可以查詢某個(gè)區(qū)間 [i, j] 內(nèi)所有元素的和

線段樹

假設(shè)一個(gè)長(zhǎng)度為 12 的線段樹，構(gòu)建結(jié)果如下：

構(gòu)建線段樹

在區(qū)間求和問題上，在葉子節(jié)點(diǎn)，顯然劃線部分的值可以由父親節(jié)點(diǎn) - 左端葉子節(jié)點(diǎn)得到。

那么，這部分信息就是冗余的，沒有保存的必要。

對(duì)于區(qū)間求和問題，劃線部分是冗余的

同理，可以推導(dǎo)出所有冗余的部分如下：

同理，所有的冗余部分

那么，去除冗余部分后的結(jié)果如下：

去除冗余部分

給每一個(gè)節(jié)點(diǎn)一個(gè)編號(hào)。

我們假設(shè) i 為每個(gè)節(jié)點(diǎn)的編號(hào)， L[i] 為該節(jié)點(diǎn)包含多少個(gè)元素的信息（就是區(qū)間內(nèi)的元素之和）。

可以得到如下表格。

序號(hào)，元素個(gè)數(shù)，二進(jìn)制表示

再來看看其二進(jìn)制表示：

每個(gè)節(jié)點(diǎn)序號(hào)和包含的元素個(gè)數(shù)

沒看出規(guī)律？

我們來分析一下：

以上增加的值對(duì)應(yīng)表中的 L[i]。

從上可以看出當(dāng)前節(jié)點(diǎn) i 的父節(jié)點(diǎn)是 i+(i的“最低位1”)，一般稱之為低位技術(shù)：L[i] = i & (-i)

那么 i 節(jié)點(diǎn)的父節(jié)點(diǎn)的序號(hào)為：i + L[i]

同樣的規(guī)律，可以推算出 [1, i] 的值的第一個(gè)區(qū)間為 ：i - L[i]

接下來上代碼：

    /* 
     * 假設(shè)樹狀數(shù)組為 T，長(zhǎng)度為 n，序號(hào) [1, ..., n]
     */
    
    // 低位技術(shù)
    #define LOWBIT(x)    ((x)&(-(x)))
    
    // 獲取區(qū)間 [1, x] 的和
    int getSum(int x) {
        int ret = 0;
        for (int i = x; i > 0; i-=LOWBIT(x)) {
            ret += T[i];
        }
        return ret;
    }
    
    // 獲取區(qū)間 [x, y] 的和
    int getSum(int x, int y) {
        return getSum(y) - getSum(x - 1);
    }
    
    // 更新第 x 點(diǎn)的值
    void updateOneNode(int x, int c) {
        for (int i = 0; i <= n; i+=LOWBIT(x)) {
            T[i] += c;
        }
    }