樹狀數組 - HackMD

# 樹狀數組 ###### 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 指的是二進位。 ![](https://i.imgur.com/aENow4o.png =700x) - 節點 $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) - 逆序數對