# 樹狀數組
###### tags: `Competitive Programming Note` `108 師大附中校隊培訓`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

[108 師大附中校隊培訓簡報](/@wiwiho/SJ615_FcB)

前綴和序列不能做修改，因為做一次修改就要用 $O(n)$ 的時間來重新算出整個序列，也就是說，每一個位置都被太多前綴和所包含了。

雖然帶修改前綴和也可以用線段樹來做，不過有一個更適合用在前綴和的可修改結構—樹狀數組／二元索引樹（Binary Indexed Tree，常簡稱 BIT）。BIT 的常數小，實作也更簡單。

BIT 的空間只要 $n$，比線段樹的 $4n$ 小，而和前綴和一樣，只需要用一個一維陣列就可以儲存一棵 BIT 了。

BIT 的每一個位置表示的值根據它的位置編號而定，$BIT_i$ 定義為：以 $A_i$ 為結尾，長度為 $lowbit(i)$ 的區間和，也就是 $[i-lowbit(i)+1,i]$ 這個範圍的和，$lowbit(i)$ 指的是把 $i$ 轉成二進位後，把最低位的 $1$ 以外的 $1$ 都變成 $0$，例如 $$lowbit((56)_{10})=lowbit((111000)_2)=(1000)_2=(8)_{10}$$

所以說，$BIT_{56}$ 就是 $[49,56]$ 這個區間的和。

要得到 $lowbit(x)$ 的方法是 `x&-x`，也就是把它和它的相反數取 bitwise and，因為 `-x` 會是 `x` 的補數加 $1$，`x` 在最低位的是 $1$ 的位元會變為 $0$，右邊的 $0$ 在取補數後會變為 $1$，加上 $1$ 之後，這些又會變為 $0$，而本來是最低位的 $1$ 的地方也會變為 $1$，但在左邊的每一個位元都會和本來不同，因為取 bitwise and 後，就可以得到 $lowbit(x)$。

節點 $0$ 代表的是一個空區間，而節點 $1$ 的區間只包含 $[1,1]$，因此，序列的索引應該要從 $1$ 開始。

那麼 BIT 畫成樹是什麼樣子？其實它並不是二元樹，binary 指的是二進位。


- 節點 $i$ 的父節點是 $i-lowbit(i)$。
- 節點 $i$ 的深度與 $i$ 是 $1$ 的位元數相同。
- 節點 $i$ 的右兄弟節點（如果有的話）是 $i+lowbit(i)$。

節點 $0$ 就是根節點，然後按照上述規則，可以畫出一棵樹。仔細觀察一下，會發現每個節點代表的區間有這些性質：

- 節點 $i$ 的父節點是 $p$，則節點 $i$ 的區間是 $[p+1,i]$，因為 $p=i-lowbit(i)$。
- 節點 $i$ 的區間包含它所有左兄弟節點的區間，因為它們的父節點都一樣，所以它們區間的起點都一樣，但 $i$ 的結束點較後面。
- 節點 $i$ 的區間包含所有左兄弟節點 $j$ 的子孫節點的區間，因為 $j$ 子孫節點區間必在 $j$ 和 $i-1$ 之間，而 $i$ 的區間肯定包含這段。

在知道這些性質後，就可以來討論怎麼處理詢問了。

## 單點修改

如果現在要修改一個位置 $pos$，那要找到所有區間包含這個位置的節點，第一個這樣的節點是 $pos$，接下來，它的所有右兄弟節點都包含這裡，用 $pos+lowbit(pos)$ 可以得到右兄弟節點，而其父節點的右兄弟節點也包含這個點，若 $pos$ 最右邊的兄弟節點是 $t$，那其父節點的右兄弟會是 $t+lowbit(t)$。

所以只要一直把 $pos$ 加上 $lowbit(pos)$，就可以得到它和它祖先的所有右兄弟節點，修改這些節點的答案就好了。

實作相當簡單：

void modify(int pos, int x){ //把pos改成x
    //n是序列大小
    for(; pos <= n; pos += lowbit(pos)){
        修改節點pos的答案;
    }
}

可以發現 $lowbit(pos)$ 會不斷增加，所以複雜度是 $O(\log n)$。

## 前綴查詢

要查詢以 $pos$ 為結尾的前綴，就應該找到幾段不重疊，且聯集恰好是所求前綴的區間。

區間以 $pos$ 為結尾的節點是 $pos$，而節點 $pos$ 的區間剛好緊接在它的父節點之後，它的父節點是 $pos - lowbit(pos)$，所以只要找到 $pos$ 和它所有祖先節點，這些區間聯集起來就是我們想要的前綴。

實作也非常簡單：

type query(int pos){
    type ans;
    for(; pos > 0; pos -= lowbit(pos)){
        更新ans;
    }
    return ans;
}

同樣地，$lowbit(pos)$ 會不斷增加，因此複雜度是 $O(\log n)$。

## 建構

建 BIT 的話，就把每一個元素分別 modify 就好了，複雜度是 $O(n \log n)$。

## 高維 BIT

和線段樹一樣，在 $D$ 維 BIT 的每個節點上存一棵 $D-1$ 維的 BIT，用法就和線段樹完全一樣。

## 應用

BIT 最基礎的應用就是拿來算前綴和，因為和是一種「可返回」的東西，減去本來的值在加上新的值就可以得到新的和，而有了前綴和就也可以算區間和了，且它比線段樹好寫很多。

BIT 前綴和和差分序列結合使用，就可以做到 $O(1)$ 區間修改、$O(\log n)$ 單點查詢。

BIT 也可以區間修改、區間查詢前綴和。先算出要做的序列 $A$ 的差分序列 $D$，$A$ 的索引從 $1$ 開始，然後我們可以得出 $[1,x]$ 這個區間的和是：
$$\sum_{i=1}^x a_i = \sum_{i=1}^x D_i \times (x-i+1)\\
=D_1 \times x + D_2 \times (x-1) + ... + D_x \times 1$$

然後可以把它化成：

$$(x+1) (\sum_{i=1}^x D_i) - (\sum_{i=1}^x D_i \times i)$$

那麼只要用兩個 BIT，一個維護 $D_i$、另一個維護 $D_i \times i$，這樣就可以做區間修改、區間求和了。

至於 BIT 可不可以做最大最小值這種「不可返回」的操作呢？如果在求最大值的數字時，把其中一個位置改小，那麼是沒辦法單靠被修改的位置就得出新的最大值的，因此如果要用 BIT 做最大值，數字只能被改大，做最小值，數字只能被改小。

## 練習題

- [ZeroJudge d799](https://zerojudge.tw/ShowProblem?problemid=d799) - 區間加值、詢問區間和
- [TIOJ 1175](https://tioj.ck.tp.edu.tw/problems/1175) - LIS
- [TIOJ 1869](https://tioj.ck.tp.edu.tw/problems/1869) - 二維 BIT
- [TIOJ 1080](https://tioj.ck.tp.edu.tw/problems/1080) - 逆序數對