5 樹狀數組

課程內容#

前綴和數組與差分數組#

【假設】原數組 $a$：$a_i,\ i\in [0,\ n]$，注意 $a_0=0$[否則差分數組的前綴和不等於原數組]

【可得】

前綴和數組 $S$：$S_i = \sum_{k=0}^{i}{a_i}$，易得 $a_i = S_i - S_{i-1}$[差分]
差分數組 $X$：$X_i=a_i-a_{i-1}$，易得 $a_i=\sum_{k=0}^{i} X_i$[前綴和]

【觀察】

前綴和數組、差分數組，並沒有增加信息，只是信息的另一種表現形式
已知一個數組，就可以推出其他數組
- 已知 $a$ 數組：—— 前綴和 ——>$S$ 數組、—— 差分 ——>$X$ 數組
- 已知 $S$ 數組：—— 差分 ——>$a$ 數組
- 已知 $X$ 數組：—— 前綴和 ——>$a$ 數組
[PS] 前綴和操作和差分操作，實際上是兩個互逆的操作
❗ 但是不同的表現形式，對不同的操作，將對應不同的時間複雜度，見下

【問題引入】

① 原數組區間和操作

$a$ 數組上操作：$O (n)$
$S$ 數組上操作：$O (1)$，由 $S_i-S_{j-1}$ 可得 $a$ 數組 $[j,\ i]$ 區間和

② 原數組區間修改操作

修改前：
- $a$ 數組上：$a_0,a_1,a_2,a_3,a_4,a_5,a_6$
- $X$ 數組上：$X_1=a_1-a_0,X_2=a_2-a_1,X_3=a_3-a_2,X_4=a_4-a_3,X_5=a_5-a_4,X_6=a_6-a_5$
修改後：[區間加]
- $a$ 數組上：$a_0,a_1,a_2 [+d],a_3 [+d],a_4 [+d],a_5 [+d],a_6$
- $X$ 數組上：$X_1=a_1-a_0,X_2=a_2-a_1 [+d],X_3=a_3-a_2,X_4=a_4-a_3,X_5=a_5-a_4,X_6=a_6-a_5 [-d]$
可見
- $a$ 數組上操作：$O (n)$
- $X$ 數組上操作：$O (1)$

【結論】

前綴和數組：優化區間和操作
差分數組：優化區間元素修改操作

【思考】❗

前綴和數組的單點修改效率是 $O (n)$，因為需要修改變化點及之後的所有前綴和元素值
前綴和數組元素值與之前原數組中所有項都有關係！那麼，如何弱化這種關係呢？

👉樹狀數組：弱化上面這種關係，損失一點查詢效率 [取捨]

lowbit 函數#

【樹狀數組中的關鍵】

$lowbit (i)$：代表 $i$ 這個數字，二進制表示的最後一位 1 的位權
計算公式：$lowbit (i) = i\ &\ (-i) = i\ &\ (\sim i + 1)$
舉例：$lowbit (10010000)$
- 得到了最右的 1 的位置，很巧妙
負數用補碼表示法：[負數的] 補碼 = [正數的] 反碼 + 1
- 例如：$-3 = ~3 + 1 = ~0011 + 1 = 1101$
- ❗ 補碼表示法將減法變成了加法 [計算機中沒有減法]

樹狀數組#

⭐樹狀數組本質上是對前綴和數組的一種優化，主要體現在單點修改操作上

直觀對比：前綴和數組#

樹狀數組中，$C [i]$ 代表從 $a [i]$ 開始的前 $lowbit (i)$ 項的和
樹狀數組更加扁平化
兩者空間消耗相同

前綴和查詢#

前綴和：$S [i]=S [i-lowbit (i)]+C [i]$
例如
- $S[7]=S[7-1]+C[7]=S[6-2]+C[6]+C[7]=C[4]+C[6]+C[7]$
- $S[12]=S[12-4]+C[12]=C[8]+C[12]$
時間複雜度：$O (log\ n)$
[PS]$(i)_2$ 中 1 的個數，即前綴和的組成元素數量

單點修改#

修改位置 $i$ 的值，需要不斷修改 $f (i)=i + lowbit (i)$ 位：$C [i],\ C [f (i)],\ C [f (f (i))],\ ...,\ until\ index\gt n$
例如
- 修改 $a [1]$：$C [1],C [2],C [4],C [8]$ < 而對於普通的前綴和數組，需要修改前 8 項 >
時間複雜度：$O (log\ n)$

小結#

$lowbit ()$ 函數：至關重要
兩種操作
- 前綴和查詢：向前統計，每次查 $i$ 的前一位 ——> $i - lowbit (i)$，直到 $i=0$
- 單點的修改：向後修改，每次修 $i$ 的後一位 ——> $i + lowbit (i)$，直到 $i>n$
時間效率
- 前綴和查詢：$O (log\ n)$，單點修改：$O (log\ n)$
- 相比最普通的前綴和數組：查詢變差，單點修改變優，綜合時間複雜度變優
使用前提：必須可以轉化成前綴和問題

隨堂練習#

HZOJ-329：弱化的整數問題#

範例輸入

範例輸出

思路
- 涉及區間修改、單點查詢操作
  - 區間修改👉差分數組的單點操作 ① [最優，詳見上文]
  - 單點查詢👉差分數組的前綴和 ②
- 既要維護前綴和 ②，又要進行單點修改 ①，所以
  - ⭐可以使用樹狀數組，維護原數組的差分數組
  - 當然也可以使用線段樹
代碼
- ❗ 將區間修改操作放在差分數組上，轉換為【單點修改】；將單點查詢操作，轉換為差分數組的求【前綴和】
- 學習樹狀數組的代碼，其實現一般都不會變 [通用性很強]
  - ⭐ 單點修改、求前綴和
- 存儲差分數組，使用一個 pre 變量記錄前一個元素
- [PS] 差分數組和前綴和數組的下標一般都是從 1 開始，因為它們的第 0 位均為 0

HZOJ-330：加強的整數問題#

範例輸入

範例輸出

思路
- 涉及區間修改、區間查詢操作
  - 區間修改👉差分數組的單點修改 ① [同上一題：OJ-329]
  - 但如何區間查詢呢？👉兩個前綴和 ②，見下
- 區間查詢問題轉換
  - ① 因為引入差分數組，所以要圍繞差分數組來對區間和問題做轉換
  - ② 區間和 $Query (l,r)=S (r)-S (l-1)$，所以重點分析 $S$ 轉換到 $X$[差分數組]
  - ③ 推導如下等式
    - $\begin{aligned}&S_i=\sum_{k=1}^ia_k=\sum_{k=1}^{i}\sum_{y=1}^{k}{X_y}\&=\sum_{k=1}^i[(i+1)X_k-k\times X_k]=(i+1)\sum_{k=1}^iX_k-\sum_{k=1}^i(k\times X_k)\end{aligned}$
    - 第一行等式顯而易見
    - 第二行等式的推導見下
      - 對於 $\sum_{k=1}^{i}\sum_{y=1}^{k}{X_y}\ (Ⅰ)$，假設 $i=4$，羅列 $k$ 值
      - 通過觀察可得，$(Ⅰ)=\sum_{k=1}^{i}[(i-k+1)\times X_k]$
      - 再將變量分組放置，即可
  - ④ 設 $Y_k=k\times X_k$，則 $S_i=(i+1)\sum_{k=1}^iX_k-\sum_{k=1}^iY_k$
  - 【結論】$S_i$ 可以通過2 個與差分數組相關的前綴和數組得到，從而完成 $Query (l,r)$ 問題
    - 需要維護兩個樹狀數組
- [PS] 維護的兩個樹狀數組，都和差分數組相關，從而保證了區間修改時的時間效率
代碼
- 關注整體思路，理清標號 $0\to 2$
- 主要方法
  - add、query 方法：樹狀數組的基本操作，單點修改 && 求前綴和
  - modify 方法：同時維護兩個樹狀數組
  - S 方法：通過 2 個差分數組的前綴和，求原序列的前綴和 [關注思路中推導的公式]
- [思考] 維護的兩個樹狀數組都與差分數組相關，所以在區間修改的時候，維護樹狀數組的時間複雜度還是 $O (log\ n)$ 級別 [2 × 2 次單點修改]
  - ❗ 如果想着區間查詢，用原數組更方便，從而維護原數組和差分數組的樹狀數組。但是，在區間修改的時候，維護原數組的樹狀數組，時間複雜度是 $O (n \times log\ n)$ 級別，還不如只用原數組，對應 $O (n)$ 級別
- [PS] 如果用 char 接收操作信息，scanf 的時候需要考慮之前換行符的存在
  - 而 cin 不會有這個問題；用字符數組也不會有這個問題

附加知識點#

樹狀數組 VS.線段樹
- 樹狀數組的代碼更少
- 空間上 ——$n：4n$[原數組大小為 $n$]

Tips#

可以聯想前綴積版樹狀數組
- 加法和乘法沒有本質的區別，它們都是積性函數
- [PS] 初始的 0 變為 1，所有 += 操作變為 *= 操作
樹狀數組的原理是什麼？—— 知乎
- 理解與 $lowbit (i)$ 的關係