進階資料結構

講些跟區間查詢修改有關的
稀疏表（Sparse Table）、樹狀數組（BIT）、線段樹（Segment Tree）
因為我簡報字太少但又沒人聽我講話所以我就打文檔給你們看你們可能比較開心

先備知識

前綴和

給定

$n$ 個數字和

$q$ 筆詢問：計算

$[l,r]$ 之間的和。(

$1\le n,q\le 2\times {10}^5$)

對每筆詢問都跑一遍

$l\sim r$。複雜度

$O(nq)$ 會炸。
但其實可以觀察到：

$$sum(l,r)=sum(1,r)-sum(1,l-1)$$
所以可以開一個陣列

$pre$ 使得

$pre[x]=\sum _{i=1}^{x}arr[i]$。只需要

$O(n)$ 預先算好。之後算區間和

$sum(l,r)=pre[r]-pre[l-1]$ 就能

$O(1)$ 解決。

2D 前綴和

如果要計算一個二維區間的和，定義

$S(X)$ 為左上角到

$X$ 的加總，則以下圖片之灰色區域面積即為

$S(A)-S(B)-S(C)+S(D)$。

實作上開一個二維陣列就行。

差分

上述提到的前綴和是

$O(n)$ 修改

$O(1)$ 查詢。差分則是

$O(1)$ 修改

$O(n)$ 查詢，思想是若要將一個區間

$[l,r]$ 加上

$x$，假設此時有一條線從頭掃過去，到

$l$ 的時候會「進入」區間，到

$r+1$ 的時候則會「退出」區間。
實作上也是相同邏輯，定義差分陣列

$dif$ 。當更新區間

$[l,r]$ 加上

$x$ 時，將

$dif[l]$ 加上

$x$，而

$dif[r+1]$ 減掉

$x$，查詢時只需要從頭做一次前綴和就可以得到每個點的值了。

Sparse Table

Sparse Table（稀疏表）可以處理靜態，且重複計算並不會影響結果的區間問題（如區間最大、最小值問題），建構時間

$O(n\log n)$ 查詢

$O(1)$。

假設要計算以下區間的最小值。

可以把問題劃分成求以下兩個區間的最小值，然後再求一次最小值，就會是整個大區間的最小值（因為重複計算最小值並不會導致結果改變）。

Implement

Build

可以先把陣列切成多個長度為二的冪次的區間，計算出他們的最小值，就可以

$O(n\log n)$ 建構。

vector<vector<int>> st(__lg(n) + 1, vector<int>(n)); // n * log n
for (int i = 0; i < n; i++) st[0][i] = arr[i]; // len = 1 時最小值等於自己
for (int i = 1; i <= __lg(n); i++) {
    int len = 1 << (i - 1); // 若當前處理長度 4 的區間，需要兩個長度 2 合併
    for (int j = 0; j + len < n; j++) {
    	st[i][j] = min(st[i - 1][j], st[i - 1][j + len]);
    }
}

Query

查詢時，設

$k$ 為不超過區間長度的最大二冪次，則區間最小值就可以透過以下公式

$O(1)$ 計算：

$$min(l,r)=min(min(l,l+k-1),min(r-k+1,r))$$

int query(int l, int r) {
    int k = __lg(r - l + 1); // 二的次方數
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

Note: __lg(x)在有些編譯器無法使用，其返回值等同於 floor(log2(x))，也可以使用以下程式碼代替

lg

int lg(int x) {
    return 31 - __builtin_clz(x);
}

Binary Indexed Tree

BIT，aka Fenwick Tree、樹狀數組、二元索引樹。雖然稱作「樹」但實際上是以陣列形式儲存。可以進行各種區間和的操作。修改

$O(\log n)$ 查詢

$O(\log n)$。
前綴和的建構需要

$O(n)$。是因為如果修改了一個元素，則後面的所有元素都要更新。
所以 BIT 結合前綴和以及剛剛 Sparse Table「分塊」的思想，將陣列按照二的冪次切割，這樣當更新時最多只會需要重新計算

$\log n$ 塊。

跟剛才的切割方式有些不同。設

$p(k)$ 為可以整除

$k$ 的最大二冪次，使：

$$tree[k]=sum(k-p(k)+1,k)$$會將陣列切格成以下

灰色方格計算了

$sum(1,7)=sum(1,4)+sum(5,6)+sum(6,7)=16+7+4=27$，對應到原先的

$sum(1,7)=1+3+4+8+6+1+4=27$。查詢複雜度為

$O(\log n)$。

Implement

$p(k)$ 為可以整除

$k$ 的最大二冪次

問題出在要怎麼計算

$p(k)$

先隨便試幾個數字

$k$	$p(k)$
$6={00110}_2$	$2={00010}_2$
$7={00111}_2$	$1={00001}_2$
$12={01100}_2$	$4={00100}_2$

發現

$p(k)$ 就等於

$k$ 的最低位元

$lowbit(k)$，觀察以下表格：

$k$	$-k$	$p(k)=lowbit(k)$
$6={00110}_2$	$-6={11010}_2$	$2={00010}_2$
$7={00111}_2$	$-7={11001}_2$	$1={00001}_2$
$12={01100}_2$	$-12={10100}_2$	$4={00100}_2$

得到

$lowbit(k)=k\mathrm{\&}-k$。
其實這個

$lowbit$ 的隱藏含義就是他包含了往前數幾個的區間（例如

$lowbit(6)=2$，就代表

$6$ 這個節點包含

$5$ 跟

$6$ 的和。）

Modify

對於每個更新的值，會影響到的區間是大於等於他的。

更新位置

$3$：

$3\to 4\to 8$，每次增加

$lowbit(k)$。

void add(int k, int x) {
    while (k <= n) {
    	tree[k] += x;
        k += k & -k;
    }
}

而如果陣列有初始值就對於

$1\sim n$ 分別跑一次就行。

Query

用一下剛才那張圖

$7\to 6\to 4$，每次減少

$lowbit(k)$。

int sum(int k) {
    int ret = 0; // return
    while (k) { // while k >= 1
    	ret += tree[k];
        k -= k & -k;
    }
    return ret;
}

要注意一下 BIT 是 1-based 的不然

$lowbit(k)$ 永遠都是

$0$

Other Technique

BIT 計算的是

$1\sim x$ 的值，如果要計算

$[l,r]$ 的區間就仿照前綴和的方式

$sum(l,r)=sum(1,r)-sum(1,l-1)$。
既然他計算的是前綴和，把 BIT 替換成計算差分，就可以區間更新單點查詢。

有了單點改值區間查詢、區間改值單點查詢，那要怎麼算區間改值區間查詢？
設原數列

$A$ 以及差分陣列

$D$，列出

$[1,x]$ 區間和公式：

$$\sum _{i=1}^x{A}_i=D_1\times x+D_2\times (x-1)+\cdots +D_x\times 1=\sum _{i=1}^x{D}_i\times (x-i+1)$$

$D_1$ 加了

$x$ 次，

$D_2$ 加了

$x-1$ 次…

把右邊的拆開得到

$$(x+1)(\sum _{i=1}^x{D}_i)-(\sum _{i=1}^x{D}_i\times i)$$只需要開兩個 BIT，一個維護

$\sum _{i=1}^x{D}_i$，一個維護

$\sum _{i=1}^x{D}_i\times i$ 就能

$O(\log n)$ 區間改值

$O(\log n)$ 區間查詢。

Segment Tree

功能最多的資料結構之一，有很多變形，能在

$O(\log n)$ 時間內達成各種區間操作，缺點就是比較難寫一點。有迭代式線段樹和遞迴式線段樹這兩種，差在實作方式不同。這篇只講最基礎的線段樹，之後會有一堂專門講線段樹課的再詳細講遞迴寫法。

先看一下他的結構（此為求和的線段樹）

因為對於一個區間，可以不斷的切成左區間和右區間兩半，查詢的複雜度為

$O(\log n)$。
以上的灰色區域

$sum(2,7)=sum(2,3)=sum(4,7)=9+17=26$。

葉節點為陣列值，每一個節點存兩個子節點的和，根節點存所有點的和。
重新編號之後：

就可以把它放進一個大小為

$2n$ 的一維陣列裡：

每個節點的父節點皆為該點編號除以二向下取整。
建構方式就是

$tree[k]=tree[k\times 2]+tree[k\times 2+1]$。若需要計算最小值則是

$tree[k]=min(tree[k\times 2],tree[k\times 2+1])$。
線段樹也可以做其他各式各樣的區間問題，甚至如位元運算（AND、OR、XOR）等。

Implement

這邊示範的線段樹皆為 1-based
用迭代式或遞迴式線段樹純看個人偏好（若是不複雜的區間問題迭代式可能較好寫，複雜的遞迴式比較容易構建且不容易寫錯。）

迭代式

迭代式就是用迴圈跑 Bottom-up，直接從葉子節點更新或查詢，一路往上。

Modify

建構（或修改）比較簡單，先將要改的位置加上

$n$ 移動到線段樹對應的位置，並且逐步更新父節點。

以上為更新原陣列值為

$7$ 的點。

void add(int k, int x) {
    k += n; // 先移到對應位置
    tree[k] += x;
    for (k /= 2; k > 0; k /= 2) {
    	tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

Query

同樣先把要查詢的區間

$[l,r]$ 加上

$n$ 移動到線段樹中相對應的位置，接下來每一次都將

$l$ 和

$r$ 往上移一層，只需要關注上移後是否會超出範圍就好，若會超出就將當前值加入並且內縮。
有點抽象，可以看著 code 畫個圖觀察看看。

int sum(int l, int r) {
	l += n, r += n;
    int ret = 0;
    while (l <= r) {
    	// 如果父節點會超出範圍就縮進來
    	if (l % 2 == 1) ret += tree[l++];
        if (r % 2 == 0) ret += tree[r--];
        l /= 2, r /= 2; // 移動到上一層
    }
    return ret;
}

遞迴式

遞迴就是用遞迴往下尋找到符合條件的區間，屬於 Top-down，從根節點出發。遞迴式線段樹要特別留意因為不是所有陣列都是為二的冪次，無法保證最後原始陣列能對應到線段樹最尾端，所以要把陣列大小開到

$n\times 4$，可以證明此大小在任何陣列長度都可以正確紀錄。

Build

雖然是可以跑一個

$O(n)$ 迴圈然後每次修改

$O(\log n)$ 在

$O(n\log n)$ 建構完。但通常還是習慣會寫一個 build 函式直接建構。

void build(int id, int l, int r, vector<int> data) {
    if (l == r) { // 對應到原陣列特定值
        tree[id] = data[l];
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid, data); // 左子節點
    build(id * 2 + 1, mid + 1, r, data); // 右子節點
    tree[id] = tree[id * 2] + tree[id * 2 + 1]; // 合併
}

Modify

// id = 節點編號 / k = 原陣列索引 / x = 加上的值 / [l, r] 為當前處理區間
void add(int id, int k, int x, int l, int r) {
    if (l == r) {
        tree[id] += x;
        return;
    }
    int mid = (l + r) / 2;
    // 該點在左子節點區間內
    if (k <= mid) modify(id * 2, k, x, l, mid);
    // 在右子節點區間內
    else modify(id * 2 + 1, k, x, mid + 1, r);
    // 更新
    tree[id] = tree[id * 2] + tree[id * 2 + 1];
}

Query

// id = 節點編號 / [l, r] 當前處理區間 / [L, R] 欲查詢區間和
int sum(int id, int l, int r, int L, int R) {
    if (l <= L && R <= r) { // 當前處理區間完全落在欲查詢區間內
        return tree[id];
    }
    int mid = (l + r) / 2;
    int ret = 0;
    // 欲查詢區間在當左子節點區間內
    if (L <= mid) ret += query(id * 2, l, mid, L, R);
    // 右子節點
    if (R > mid) ret += query(id * 2 + 1, mid + 1, r, L, R);
    return ret;
}

題目

Basics

Static Range Sum Queries
Forest Queries

Sparse Table

Static Range Minimum Queries

BIT

Dynamic Range Sum Queries
Range Update Queries

Segment Tree

Dynamic Range Minimum Queries
Range Xor Queries

參考資料

1. Competitive Programmer's Handbook
   Laaksonen, A. (2018, July 3). Competitive Programmer's Handbook [PDF]. https://cses.fi/book/book.pdf
2. Fenwick Tree
   (n.d.). Fenwick Tree. https://cp.wiwiho.me/fenwick-tree/