樹狀數組 複習與整理
- 2019 年 11 月 8 日
- 筆記
rt。用(LaTeX)整理了公式。
之前那篇很混亂而且咕咕咕到現在的隨筆：st表、樹狀數組與線段樹 筆記與思路整理
一、構成方式
樹狀數組是一種樹狀的結構（廢話），但是只需要 $ O(n)$ 的空間複雜度。區間查詢和單一修改時間複雜度都為 (O(log n)) ，利用差分區間修改也可以達到 (O(log n)) ，但此時不能區間查詢。通過維護兩個數組可以達到 (O(log n)) 的區間修改與查詢。
樹狀數組是基於一棵二叉樹，為便于思想上向數組轉化，這裡稍微變形：（Excel繪圖23333）
如果要在一棵樹上存儲一個數組並且便於求和，我們可以想到讓每個父節點存儲其兩個子節點的和。（就決定是你啦！線段樹！）
為了達到 (O(n)) 的空間複雜度，刪去一些節點（放棄線段樹）後如下：
標有序號的節點為樹狀數組，序號從左向右增大。
二、運算規律
觀察上一節的圖可得，每個樹狀數組的節點都儲存了(2^k)個原數組節點的數據（(k)為節點深度）。也就是說，在上面的圖中：
t[1] = a[1]; t[2] = a[1] + a[2]; t[3] = a[3]; t[4] = a[1] + a[2] + a[3] + a[4]; t[5] = a[5]; t[6] = a[5] + a[6]; t[7] = a[7]; t[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8];所以說，這棵樹的（不是我自己推出來的）規律是：
[t[i] = a[i – 2^k + 1] + a[i – 2^k + 2] + … + a[i]]
//(k)為(i)的二進位中從最低位到高位連續零的長度
將(2^k)稱為(lowbit(i))，則程式碼如下：
void add(int pos, int val){ //將節點pos增加val for(int i=pos; i<=n; i+=lowbit(i)){ t[i] += val; } } int ask(int pos){ //求節點pos前綴和 int ans = 0; for(int i=pos; i>0; i-=lowbit(i)){ ans += t[i]; } return ans; } int query_sum(int l, int r){ //利用前綴和求[l, r]總和 return ask(r) - ask(l); }那麼問題來了，怎麼求這個 (2^k) 呢？
有一個巧妙的（我自己也沒推出來的）演算法是：
[lowbit(x) = x & (-x)]
抄一段證明如下：
這裡利用的負數的存儲特性，負數是以補碼存儲的，對於整數運算 (x&(-x))有
● 當(x)為(0)時，即 (0 & 0)，結果為(0)；//因此實際運算的時候如果真的出現了(lowbit(0))會卡死，要從(1)開始存儲
●當(x)為奇數時，最後一個比特位為(1)，取反加(1)沒有進位，故(x)和(-x)除最後一位外前面的位正好相反，按位與結果為(0)。結果為(1)。
●當(x)為偶數，且為(2^m)時，(x)的二進位表示中只有一位是(1)（從右往左的第(m+1)位），其右邊有(m)位(0)，故(x)取反加(1)後，從右到左第有(m)個(0)，第(m+1)位及其左邊全是(1)。這樣，(x& (-x)) 得到的就是(x)。
●當(x)為偶數，卻不為(2^m)的形式時，可以寫作(x= y times (2^k)) 。其中，(y)的最低位為(1)。實際上就是把(x)用一個奇數左移(k)位來表示。這時，(x)的二進位表示最右邊有(k)個(0)，從右往左第(k+1)位為(1)。當對x取反時，最右邊的(k)位(0)變成(1)，第(k+1)位變為(0)；再加(1)，最右邊的(k)位就又變成了(0)，第(k+1)位因為進位的關係變成了(1)。左邊的位因為沒有進位，正好和(x)原來對應的位上的值相反。二者按位與，得到：第(k+1)位上為(1)，左邊右邊都為(0)。結果為(2^k)。
總結一下：(x&(-x))，當(x)為(0)時結果為(0)；(x)為奇數時，結果為(1)；(x)為偶數時，結果為(x)中(2)的最大次方的因子。
三、具體操作
1.區間查詢單點修改
如上文所說，使用循環維護一條樹上路徑即可。
模板題： 洛谷 P3374
查看源碼
#include "bits/stdc++.h" using namespace std; int a[500010], t[500010]; int n, m; int lowbit(int x){ return x & (-x); } void add(int pos, int val){ for(int i=pos; i<=n; i+=lowbit(i)){ t[i] += val; } } int query_node(int pos){ int ans = 0; for(int i=pos; i>0; i-=lowbit(i)){ ans += t[i]; } return ans; } int query_range(int l, int r){ return query_node(r) - query_node(l-1); } int main(){ cin >> n >> m; int opt, pos, l, r, num; for(int i=1; i<=n; i++){ scanf("%d", &a[i]); add_node(i, a[i]); } while(m--){ scanf("%d", &opt); if(opt == 1){ scanf("%d%d", &pos, &num); add_node(pos, num); } if(opt == 2){ scanf("%d%d", &l, &r); printf("%dn", query_range(l, r)); } } return 0; }2.單點查詢區間修改
利用差分的思想，設數組(b[i]=a[i]-a[i-1])，用樹狀數組(t[~])表示(b[~])。(這裡默認(a[0]=b[0]=0))
來一組樣例：
(a[~]={1,~5,~4,~2,~3,~1,~2,~5})
(b[ ] = { 1, 4, -1, -2, 1, -2, 1, 3})
處理區間([1, 5])，將其中所有元素+1：
(a[~]={1,~{color{red}{6,~5,~3,~4,~2,}}~2,~5})
(b[ ] = { 1, {color{red}5,} -1, -2, 1, -2, {color{red}0,} 3 })
可以看到，只有 (b[1]) 和 (b[6]) 發生了變化。（即更改區間([l, r])時的節點(l)與節點(r+1)）因此，以 (b[ ]) 為原數組的 (t[ ]) 只需要執行兩次 (add()) 即可。但是，在查詢 (a[i]) 的時候就需要查詢 (b[1...i]) 之和，在 (log n) 時間裡只能查詢單個節點的值。
模板題：洛谷 P3368
查看源碼
#include "bits/stdc++.h" using namespace std; int a[500010], t[500010]; int n, m; int lowbit(int x){ return x & (-x); } void add_node(int pos, int val){ for(int i=pos; i<=n; i+=lowbit(i)){ t[i] += val; } } void add_range(int l, int r, int val){ add_node(l, val); add_node(r+1, -val); } int query_node(int pos){ int ans = 0; for(int i=pos; i>0; i-=lowbit(i)){ ans += t[i]; } return ans; } int main(){ cin >> n >> m; int opt, pos, l, r, num; for(int i=1; i<=n; i++){ scanf("%d", &a[i]); add_node(i, a[i] - a[i-1]); } while(m--){ scanf("%d", &opt); if(opt == 1){ scanf("%d%d%d", &l, &r, &num); add_range(l, r, num); } if(opt == 2){ scanf("%d", &pos); printf("%dn", query_node(pos)); } } return 0; }3.區間查詢區間修改
關於區間查詢與區間修改的操作，考慮維護兩個樹狀數組來優化差分：
（本段參考了xenny的部落格）
(sum_{i=1}^{n}a[i] =sum_{i=1}^n sum_{j=1}^it[j])
則
[ begin{align*}& a[1] + a[2] + ... + a[n]\ = ~&(t[1]) + (t[1] + t[2]) + ... + (t[1] + t[2] + ... + t[n]) \ = ~&n * t[1] + (n-1) * t[2] + ... + t[n]\ =~& n * (t[1] + t[2] + ... + t[n]) - (0 * t[1] + 1 * t[2] + ... + (n - 1) * t[n])end{align*} ]
所以上式可以變為(∑^n_{i = 1}a[i] = n∑^n_{i = 1}t[i] - ∑^n_{i = 1}( t[i] * (i - 1) ))
因此，實現了區間查詢與區間修改之後可以實現線段樹的某些功能。但這種實現方式與線段樹還有所差異，詳情見下一節「優勢與局限」。
模板題：洛谷 P3372 （線段樹模板1）
查看源碼
#include "bits/stdc++.h" using namespace std; typedef long long ll; ll a[500010], t1[500010], t2[500010]; int n, m; int lowbit(int x){ return x & (-x); } void add_node(int pos, ll val){ for(int i=pos; i<=n; i+=lowbit(i)){ t1[i] += val; t2[i] += val * (pos-1); } } void add_range(int l, int r, int val){ add_node(l, val); add_node(r+1, -val); } ll quary_node(int pos){ ll ans = 0; for(int i=pos; i>0; i-=lowbit(i)){ ans += pos * t1[i] - t2[i]; } return ans; } ll quary_range(int l, int r){ return quary_node(r) - quary_node(l-1); } int main(){ cin >> n >> m; int opt, pos, l, r; ll num; for(int i=1; i<=n; i++){ scanf("%d", &a[i]); add_node(i, a[i] - a[i-1]); } while(m--){ scanf("%d", &opt); if(opt == 1){ scanf("%d%d%lld", &l, &r, &num); add_range(l, r, num); } if(opt == 2){ scanf("%d %d", &l, &r); printf("%lldn", quary_range(l, r)); } } return 0; }四、優勢與局限
很顯然，在相同的實現下（區間查詢、區間修改），樹狀數組的碼量要小於線段樹等，運行時的常數與佔用空間也較小。
但實際上，樹狀數組只能維護前綴操作和（前綴和，前綴積，前綴最大最小），而線段樹可以維護區間操作和。
使用樹狀數組來「維護區間操作和」的實現，本質上是取右端點的前綴和，然後對左端點左邊的前綴和的逆元做一次操作。因此，如果不存在逆元的操作（乘法（P.s.:模不為質數）、區間最值等）就無法用樹狀數組完成。
此段參考資料：關於線段樹(Segment tree)和樹狀數組(BIT)的區別？-知乎
