線段樹 (Segment Tree)
支援單點修改的區間和查詢
給定一個長度為 的序列 和 筆操作，有兩種操作：
1 x v：將 改成 。2 x y：詢問 之間的和。
線段樹是一種常用來於處理區間查詢及修改的題目，根節點紀錄 之間的數據，令每個紀錄 節點 ，令 ，左子節點為 ，右子節點為 。
儲存
線段樹可以用和 Complete Binary Tree 一樣的方式儲存（雖然不完全是 Complete Binary Tree），一般來說會開大小為 的陣列避免編號超出陣列範圍。
除了陣列，指標也可用來實作線段樹，但指標實作較容易出錯，建議非必要不用指標實作。
| // 陣列版本
#define LC(x) ((x << 1)) // 左子節點的 ID
#define RC(x) ((LC(x)) | 1) // 左子節點的 ID
int seg[(N << 4)];
// 指標版本
struct Node{
Node *lc, *rc;
};
|
單點修改
假設要更新的位置為 ，那麼所有包含 的節點就要更新。從起點開始，遍歷所有包含 的節點，最深的節點為 。 直接更新值，其他遍歷的節點 則是根據 和 的值合併。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | void update(int rt, int L, int R, int qL, int qR, int val)
{
if (qL <= L && R <= qR)
{
seg[rt] = val;
return;
}
int M = (L + R) >> 1;
if (qL <= M)
update(LC(rt), L, M, qL, qR, val);
if (M + 1 <= qR)
update(RC(rt), M + 1, R, qL, qR, val);
seg[rt] = seg[LC(rt)] + seg[RC(rt)];
}
|
每次往下一層節點區間長度會減半，最多往下 層，時間複雜度為 。
初始化寫法
有一些人會寫一個 build 函式遍歷並更新所有節點，時間複雜度為 。
1
2
3
4
5
6
7
8
9
10
11
12 | void build(int rt, int L, int R, vector<int> &v)
{
if (qL <= L && R <= qR)
{
seg[rt] = v[L];
return;
}
int M = (L + R) >> 1;
build(LC(rt), L, M, v);
build(RC(rt), M + 1, R, v);
seg[rt] = seg[LC(rt)] + seg[RC(rt)];
}
|
另一種方式是利用 次單點修改初始化線段樹，時間複雜度為 。
不論哪種寫法，都不會影響最終的時間複雜度。
區間查詢
支援區間修改的區間和查詢
給定一個長度為 的序列 和 筆操作，有兩種操作：
1 x y v：將 到 改成 。2 x y：詢問 之間的和。
假設要查詢的範圍 ，要找出所有節點 其中 。
1
2
3
4
5
6
7
8
9
10
11
12 | int query(int rt, int L, int R, int qL, int qR)
{
if (qL <= L && R <= qR)
return seg[rt];
int M = (L + R) >> 1;
if (qR < M + 1)
return query(LC(rt), L, M, qL, qR);
else if (M < qL)
return query(RC(rt), M + 1, R, qL, qR);
else
return query(LC(rt), L, M, qL, qR) + query(RC(rt), M + 1, R, qL, qR);
}
|
符合的區間最多有 個，最多會拜訪 個節點，時間複雜度 。
區間修改
假設要修改的範圍 ，仿效區間查詢的思維，更新所有節點 其中 ，並在該節點上新增一個懶人標記，當要拜訪 的子節點時，會將懶人標記傳遞給 的子節點。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | void push(int rt, int L, int R)
{
if(tag[rt]==-1)
return;
int M = (L + R) >> 1;
tag[LC(rt)] = tag[rt];
seg[LC(rt)] = (M - L + 1) * tag[rt];
tag[RC(rt)] = tag[rt];
seg[RC(rt)] = (R - M) * tag[rt];
tag[rt] = -1;
}
void update(int rt, int L, int R, int qL, int qR, int val)
{
if (qL <= L && R <= qR)
{
seg[rt] = (R - L + 1) * val;
tag[rt] = val;
return;
}
push(rt, L, R);
int M = (L + R) >> 1;
if (qL <= M)
update(LC(rt), L, M, qL, qR, val);
if (M + 1 <= qR)
update(RC(rt), M + 1, R, qL, qR, val);
seg[rt] = seg[LC(rt)] + seg[RC(rt)];
}
int query(int rt, int L, int R, int qL, int qR)
{
if (qL <= L && R <= qR)
return seg[rt];
push(rt, L, R);
int M = (L + R) >> 1;
if (qR < M + 1)
return query(LC(rt), L, M, qL, qR);
else if (M < qL)
return query(RC(rt), M + 1, R, qL, qR);
else
return query(LC(rt), L, M, qL, qR) + query(RC(rt), M + 1, R, qL, qR);
}
|
時間複雜度 ，原因和區間查詢相同。
應用
可用來查詢區間總和或極值，支援區間修改，不支援區間刪除、翻轉。
例題練習
Codeforces 747F - Igor and Interesting Numbers
給定一個長度為 的數列 ，給定 筆詢問 之間有幾個數不能整除該區間至少一個數。
能整除所有的數，只有該區間最大公因數，利用線段樹維護區間 GCD，查詢時計算 之間有幾個數字 該區間的 GCD。
