# 進階資料結構與莫隊算法—二元索引樹 ###### tags: `108 師大附中校隊培訓` ###### wiwiho --- 前綴和序列不能做修改 那有沒有可以做修改的用來算前綴和的東西？ ---- 雖然帶修改前綴和也可以用線段樹來做 但是有更適合用在前綴和的 就是二元索引樹 （Binary Indexed Tree，常簡稱 BIT） --- BIT 只需要用一個一維陣列來存 空間只要 $n$ 比線段樹的 $4n$ 小 --- 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)$ 的方法 ---- ```cpp x&-x ``` 把它和它的相反數取 bitwise and ---- 節點 $0$ 代表的是一個空區間 而節點 $1$ 的區間只包含 $[1,1]$ 因此，序列的索引應該要從 $1$ 開始 --- ## BIT 畫成樹是什麼樣子？ ----  ---- - 節點 $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 做最大值 數字只能被改大 做最小值 數字只能被改小