所有更新在語雀發布，到原文食用體驗更佳！注冊語雀請用此鏈接
樹狀陣列詳解
引入
先問幾個問題，
什么是線段樹？
線段樹是一種資料結構，支持 \(\log\) 級別的區間修改查詢操作，
為什么要有線段樹？
用陣列實作區間查詢，區間修改是 \(O(n)\) 的，但用樹狀陣列是 \(O(\log n)\)，
樹狀陣列和線段樹的對比？
名字不一樣- 兩個都是 \(\log\) 級資料結構
- 樹狀陣列支持區間查詢，區間修改，但線段樹支持基本上所有區間操作（\(\log n\) 時間）
- 樹狀陣列空間復雜度 \(n\)，常數小；線段樹空間復雜度 \(4n\)，常數較大，
樹狀陣列原理介紹
前置芝士：
位運算
大意：
按位與：在二進制中對每一位進行對應操作：1&1=1,1&0=0,0&1=0,0&0=0
二叉樹
大意：
二叉樹的定義：每個節點至多有 2 個兒子的樹，
原理
首先上一張二叉樹的圖：（為了方便將節點右對齊）
圖片來源：https://www.cnblogs.com/xenny/p/9739600.html，已經過博主同意，下同，
是不是看著有些熟悉呢？沒錯，這就是線段樹，
但是樹狀陣列可不長這樣，前面說過它的空間復雜度是 \(n\)，
那樹狀陣列是什么樣呢？
我們將每一列都只留最上面的節點，就變成了這樣：
我們發現：（設原陣列是 a[]，樹狀陣列是 c[]）
c[1] = a[1]
c[2] = a[1] + a[2]
c[3] = a[3]
c[4] = a[1] + a[2] + a[3] + a[4]
c[5] = a[5]
c[6] = a[5] + a[6]
c[7] = a[7]
c[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]
找規律發現：\(c[i] = \sum_{j = i - \text{lowbit}(i) + 1}^i a_j\)
其中 lowbit(i) 表示 i 在二進制下最后一個 1，
例如：（下面的數都是二進制下的）
lowbit(1111) = 1
lowbit(1100) = 100
lowbit(1010) = 10
lowbit(1001) = 1
lowbit(1000) = 1
...
那么這個 lowbit 怎么求呢？不難發現有很多求法，例如：
x = 1001010
~x = 0110101
~x + 1 = 0110110
容易發現 x 與 ~x + 1 除了 lowbit 位相同，其它的都不同（顯然），所以我們得出 lowbit(i) = x & ((~x) + 1)，然后因為 (~x) + 1 就是 -x（參見原碼補碼反碼詳解），所以 lowbit(x) = x & -x，
于是我們成功處理了 lowbit！
應用
說了這么多，樹狀陣列到底是怎么維護區間的呢？
維護區間有四種，分別是：
- 單點修改，單點查詢
- 單點修改，區間查詢
- 區間修改，單點查詢
- 區間修改，區間查詢
下面來分別講解，
單點修改，單點查詢
傳統陣列即可，
單點修改，區間查詢
再來看一下這個圖：
發現 \(\sum_{i = 1}^k a_i = c(i) + c(i - lowbit(i)) + c(i - lowbit(i) - lowbit\left(i - lowbit(i)\right) + \cdots + c(1)\)
證明：
上面看不懂沒關系，用代碼也許好理解些：
int sum = 0, k;
while(k > 0) {
sum += c[k];
k -= lowbit(k);
}
// 此時 sum 值為 a[1] + a[2] + ... + a[k]
現在我們就解決了區間查詢，但如何修改呢？
我們需要將包含 \(a_i\) 的 c 都修改，
即 \(c(i)\), \(c(i + lowbit(i))\), \(c(i + lowbit(i) + lowbit(i + lowbit(i)))\), \(\cdots\)
即：
int add, k;
while(k <= n) {
c[k] += add;
k += lowbit(i);
}
// 此時已經將 a[k] += add 的修改加到樹狀陣列中了
到此為止，我們就解決了區間查詢，單點修改，
區間修改，單點查詢
前置芝士
差分陣列
大意：
設 \(t(i) = \sum_{j = 1}^i a_j\)
那么 \(a_i = \sum_{j = 1}^i t(j)\)
講解
樹狀陣列可以維護單點修改，區間查詢，但如何實作區間修改，單點查詢呢？
我們可以用維護 a 的差分陣列，而不是 a 陣列，此時區間修改 \([l, r]\) 可以轉化成 a[l] += add, a[r + 1] -= add，即單點修改；單點查詢 \(a_x\) 可以轉化成詢問 \([1, x]\) 的和，即區間查詢，
完美！
區間修改，區間查詢
仍然利用差分：
\[\begin{aligned} \sum_{i = 1}^k a_i &= (t(1)) + (t(1) + t(2)) + (t(1) + t(2) + t(3)) + \cdots + \sum_{i = 1}^k t(i)\\ &= \sum_{i = 1}^k \sum_{j = 1}^i a_j\\ &= \sum_{j = 1}^k \sum_{i = j}^k a_j\\ &= \sum_{j = 1}^k a_j \times (k - j + 1)\\ &= (k + 1) \sum_{j = 1}^k a_j - \sum_{j = 1}^k a_j \times j \end{aligned}\]然后就可以維護兩個樹狀陣列，一個 \(a_i\)，一個 \(a_i \times i\)，
題目推薦
洛谷 P3374
洛谷 P3368
參考：https://www.cnblogs.com/xenny/p/9739600.html
圖片來源：https://www.cnblogs.com/xenny/p/9739600.html
關于著作權：可以轉載或以任何形式借用，但均需注明出處，（圖片請注明上面的鏈接，不要注明我的）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235325.html
標籤：其他
下一篇：不復雜的空間復雜度