Skip to content

線段樹 (Segment Tree)

支援單點修改的區間和查詢

給定一個長度為 的序列 和 筆操作，有兩種操作：

  • 1 x v：將 改成 。
  • 2 x y：詢問 之間的和。

線段樹是一種常用來於處理區間查詢及修改的題目，根節點紀錄 之間的數據，令每個紀錄 節點 ，令 ，左子節點為 ，右子節點為 。

儲存

線段樹可以用和 Complete Binary Tree 一樣的方式儲存（雖然不完全是 Complete Binary Tree），一般來說會開大小為 的陣列避免編號超出陣列範圍。

除了陣列，指標也可用來時做線段樹。

1
2
3
4
5
6
7
8
9
// 陣列版本
#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，時間複雜度 。

區間修改

假設要修改的範圍 ，仿效區間查詢的思維，更新所有節點 其中 ，並在該節點上新增一個懶人標記，當要拜訪 的子節點時，會將懶人標記傳遞給 的子節點。

 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);
}

時間複雜度 ，原因和區間查詢相同。

應用

可用來查詢區間總和或極值，支援區間修改，不支援區間刪除、翻轉。

  1. Implementation - Competitive Programming Algorithms ↩