樹狀數組

tags: Competitive Programming Note 108 師大附中校隊培訓

本文已停止更新，新版請至 WiwiHo 的競程筆記

108 師大附中校隊培訓簡報

前綴和序列不能做修改，因為做一次修改就要用

$O(n)$ 的時間來重新算出整個序列，也就是說，每一個位置都被太多前綴和所包含了。

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

BIT 的空間只要

$n$，比線段樹的

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

BIT 的每一個位置表示的值根據它的位置編號而定，

$BI{T}_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}$$

所以說，

$BI{T}_{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]$ 這個區間的和是：

$$\begin{gathered} \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 \end{gathered}$$

然後可以把它化成：

$$(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 - 區間加值、詢問區間和
• TIOJ 1175 - LIS
• TIOJ 1869 - 二維 BIT
• TIOJ 1080 - 逆序數對