線段樹

一些本文使用的實作習慣：

• 所有區間都是左閉右閉。
• 要把區間 分成兩半時，令 ，左半是 ，右半是 。

從分治到線段樹

有一個序列 ，有 筆詢問，詢問有兩種：

1. 把 加上
2. 求 的最大值

先想想看如果我們只是要問一次某個區間的最大值要怎麼做。最暴力的作法就是在第一種操作時直接把值改掉，第二種操作暴力掃過一次陣列，不過這樣的作法好像沒有什麼可發展性，所以我們來看一個感覺有點殺雞用牛刀的作法：

我們對整個陣列分治，令 query(l,r,L,R) 會回傳區間 與區間 交集的這個區間的最大值，並且假設我們呼叫時這個交集都不是空的。[l,r] 是我們想要知道最大值的範圍，所以我們要做的事情是每次都把 [L,R] 分成兩半，並且遞迴下去做。

1
2
3
4
5
6
7
8
9
10

int query(int l, int r, int L, int R){
    if(L == R) return a[L];
    int M = (L + R) / 2;
    if(r <= M) // [l,r] 只在左半部
        return query(l, r, L, M);
    else if(l > M)  // [l,r] 只在右半部
        return query(l, r, M + 1, R);
    else  // [l,r] 跨越兩半
        return max(query(l, r, L, M), query(l, r, M + 1, R));
}

這樣做有什麼好處呢？考慮一下分治過程，把所有分治時可能出現的 節點畫成一棵樹，並且把我們詢問 時走過的節點標記起來，會像是這樣：

這是一個 的例子，有塗顏色的點是詢問時有走過的點。這個作法需要花的時間是 ，要是 是 ，那所有點都會被走過，因此時間複雜度是 。

注意到有一些點，我們會走到它為根的子樹裡全部的點，這些點是滿足 的點，要是我們預先算好每一個點的區間內最大值是多少，就可以在走到一個滿足這個條件的點時，直接回傳最大值，而不需要再往子樹裡走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#define lc 2 * id
#define rc 2 * id + 1
void build(int L, int R, int id){
    if(L == R){
        mx[id] = a[id];
        return;
    }
    int M = (L + R) / 2;
    build(L, M, lc);
    build(M + 1, R, rc);
    mx[id] = max(mx[lc], mx[rc]);
}
int query(int l, int r, int L, int R, int id){
    if(l <= L && R <= r) return mx[id];
    int M = (L + R) / 2;
    if(r <= M)
        return query(l, r, L, M, lc);
    else if(l > M) 
        return query(l, r, M + 1, R, rc);
    else 
        return max(query(l, r, L, M, lc), 
                   query(l, r, M + 1, R, rc));
}

先 build(1, N, 1) 找出所有節點對應區間的最大值，之後就可以用 query(l, r, 1, N, 1) 詢問。計算最大值時發揮分治的精神，從子節點（兩半部）的資訊（最大值）得出這個節點（整個區間）的資訊。

為了方便儲存每個節點的最大值，我們給每個節點一個編號。這裡的根節點編號是 1，節點 的左子節點是 ，右子節點則是 。這種編號方式所使用的節點編號最大會 ，所以可以用一個長度 的陣列儲存最大值，也有一些其他不同的方法，後面的章節會再細講。

build 需要 的時間，那麼一次詢問要多少時間呢？這樣的作法中，我們只會走到上面那張圖裡紅色與藍色的節點，藍色的節點就是我們遇到 l <= L && R <= r 然後直接回傳記錄的最大值的時候，也就是遞迴的終止節點。仔細觀察一下，其實紅色與藍色的節點們都一定是「對應到 和 的節點的祖先，以及它們祖先的兄弟」，而因為樹深度是 ，因此一次詢問的時間複雜度是 。

現在我們已經可以處理快速處理多次詢問了，那麼加上修改呢？注意到我們詢問時需要的資訊就只有每個節點儲存的區間最大值而已，因此我們只要想辦法維護這些資訊。修改 時，最大值會改變的節點就是所有包含區間 的節點，也就是 對應的節點的所有祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 把 a[x] 改成 v
void modify(int x, int v, int L, int R, int id){
    if(L == R){ // 節點對應的區間是 [x,x]
        mx[id] = v;
        return;
    }
    int M = (L + R) / 2;
    if(x <= M) // x 在左半部
        modify(x, v, L, M, lc);
    else // x 在右半部
        modify(x, v, M + 1, R, rc);
    // 重新用子節點的最大值計算這個節點的最大值
    mx[id] = max(mx[lc], mx[rc]);
}

這樣一來一次修改的時間就和深度相同，是 ，我們就成功做出這個問題了！

這棵把分治過程畫出來的樹就是我們所稱的線段樹。線段樹大致上來說可以視為是在將分治的過程記錄下來，線段樹最重要的是應用到分治將一個區間分成 個區間，也就是上面的遞迴終止節點將詢問的區間分成互不相交的 段，以及用到深度很小易於查詢與修改的性質。

線段樹不只可以算最大值，像區間總和也可以算，只要記錄每個節點的區間總和，詢問時將所有終止節點的區間和加起來（因為它們的範圍是互不重疊的）就好。

線段樹的節點編號

前面的實作中，我們用一個陣列儲存線段樹節點的資訊，因此需要給線段樹每個節點一個編號。

剛剛使用的方法是，根節點的編號是 1， 的左子節點編號是 ，右子節點編號是 。這個編號方式和通常用於編號完全二元樹（complete binary tree，除了最後一層以外每一層的節點數量都是最大值，且最後一層節點靠左的二元樹）中節點的方式一樣。這種編號的二進位會是最高位的 1，後面的 bit 表示從根節點走到那個節點的方法，0 代表往左、1 代表往右。畫出來的話，看起來會是深度 0 的節點編號是 、深度 1 的是 、深度 2 的是 ，依此類推。

一棵 個節點的線段樹，在這種編號方式用到的最大節點編號 。假設我們將線段樹填滿成一棵高度相同，節點數量最大的二元樹，這個數量就是我們可能會用到的最大編號。這個數量會是 ，深度恰為 ，因此數量不超過是 。

節點也有一些別的編號方法，像是根節點是 0， 的左右子節點分別是 和 ，就只是上面那種編號都少 1 的版本而已。

還有一種神奇的編號方式是區間是 的節點編號是 (L + R) | (L != R)，這樣每個節點的編號都會是不重複的，因為：

• 當 也就是節點是非葉節點、 L != R 是 1 時，不難發現到每個節點的 也就是子節點區間的分界點都不一樣，換句話說 (L + R) >> 1 都不一樣，因此 (L + R) | 1 也會不一樣。
• 當 時，很明顯地 都不一樣，而且 一定是偶數，而非葉節點編號一定是奇數，所以不會和非葉節點衝突。

這樣就只會用到 以內的編號（沒有非葉節點的 會是 ）。

指標型線段樹

存二元樹的方法不是只有陣列，當然也有存左右子節點的指標，實作通常是直接幫每個節點開一個 struct：

1
2
3
4

struct Node{
    Node *l, *r;
    // 其他節點資訊
}

也可以使用偽指標（memory pool），就是一樣用一個陣列存節點資訊，但是在節點上存左右子節點在那個陣列中的位置。實作上可以用一個變數儲存現在陣列裡放了多少東西，每次需要新的節點（例如 build 或動態開點）時，就把這個數量 +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
43
44
45

struct Node{
    int mx;  // 區間最大值
    int tag; // 子樹裡所有人都要加上 tag
};

vector<Node> seg;

// 節點 id 的整個區間要加上 tag
void addtag(int tag, int id){
    seg[id].mx += tag; // 最大值會加上 tag
    seg[id].tag += tag; // 注意可能本來就有標記了，所以是 +=
}

// 更新子節點資訊並把標記移到子節點身上
void push(int id){
    addtag(seg[id].tag, lc);
    addtag(seg[id].tag, rc);
    seg[id].tag = 0; // 標記被移到子節點上所以要改成 0
}

// 區間 [l,r] 加上 v
void modify(int l, int r, int v, int L, int R, int id){
    if(l <= L && R <= r){
        addtag(v, id);
        return;
    }
    push(id);
    if(r <= M) modify(l, r, v, L, M, lc);
    else if(l > M) modify(l, r, v, M + 1, R, rc);
    else{
        modify(l, r, v, L, M, lc);
        modify(l, r, v, M + 1, R, rc);
    }
    seg[id].mx = max(seg[lc].mx, seg[rc].mx);
}

int query(int l, int r, int L, int R, int id){
    if(l <= L && R <= r) return seg[id].mx;
    push(id);
    int M = (L + R) / 2;
    if(r <= M) return query(l, r, L, M, lc);
    else if(l > M) return query(l, r, M + 1, R, rc);
    else return max(query(l, r, L, M, lc), 
                    query(l, r, M + 1, R, rc));
}

這個標記就被稱作懶人標記，而把標記移到子節點身上的這個動作被稱為下推標記。

注意到 modify 往下走時有時可以不需要 push，像在這邊其實可以不用，不過在操作沒有交換律（做事順序會影響結果）的時候就會需要，例如如果操作是區間改成同一個值，那麼就會需要在修改時 push，因為沒有 push 的話，子孫的新標記可能之後會被祖先的舊標記蓋掉。

這樣一來區間修改的複雜度就和區間詢問一樣是 了。

線段樹的框架

如上所說，線段樹不一定是詢問最大值，修改也不一定是加值。基本上，只要維護的資訊是父節點的資訊能從兩個子節點的資訊得出、操作有結合律（可以把相鄰的操作合起來）就能用線段樹維護。以下是一個基本的線段樹框架：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#define lc (id 的左子節點)
#define rc (id 的右子節點)

struct Node{
    Info info; // 線段樹上儲存的資訊
    Tag tag; // 懶人標記
};

vector<Node> seg; // 存線段樹的陣列

void pull(int id){ /* 從 id 的子節點資訊更新 id 的資訊 */ }
void addtag(Tag tag, int id){
    seg[id].info = 用 tag 更新 seg[id].info;
    seg[id].tag += tag;
}
void push(int id){
    addtag(seg[id].tag, lc);
    addtag(seg[id].tag, rc);
    // 把 seg[id].tag 清空
}

void build(int L = 1, int R = N, int id = 1){
    if(L == R){
        // 從原始資料算 seg[id].info
        return;
    }
    int M = (L + R) / 2;
    build(L, M, lc);
    build(M + 1, R, rc);
    pull(id);
}

void modify(int l, int r, Tag v, int L, int R, int id){
    if(l <= L && R <= r){
        addtag(v, id);
        return;
    }
    push(id);
    if(r <= M) modify(l, r, v, L, M, lc);
    else if(l > M) modify(l, r, v, M + 1, R, rc);
    else{
        modify(l, r, v, L, M, lc);
        modify(l, r, v, M + 1, R, rc);
    }
    pull(id);
}

Info query(int l, int r, int L, int R, int id){
    if(l <= L && R <= r) return seg[id].info;
    push(id);
    int M = (L + R) / 2;
    if(r <= M) return query(l, r, L, M, lc);
    else if(l > M) return query(l, r, M + 1, R, rc);
    else return query(l, r, L, M, lc) +
                query(l, r, M + 1, R, rc));
}

Tag 是表示修改資訊（懶標其實就是在把修改資訊記在結點上），例如要加上多少、要改成什麼等等。Tag 的相加是表示將兩個操作合起來，例如加上 再加上 可以合成加上 ，而 Info 相加則是把兩個節點的資訊拼起來，例如在上面的例子中是把兩個數取 max。

節點上可以維護很多資訊，像是當然可以同時維護最小值和最大值，有時也需要存一些不會改變的資訊，例如在詢問區間和並支援區間加值時，就會需要在節點上存區間大小，也可以在 addtag 時傳入區間大小，因為更新區間總和是，區間總和會加上「要加的值乘上區間大小」。

線段樹也可以一次支援很多種操作，只是這樣在結合兩個操作時需要注意一下順序。例如要同時支援區間加值和區間改值，可以在每個節點記錄要加多少和要改成什麼，打懶標或下推懶標時就要注意怎麼修改節點的懶標。

還有例如同時支援區間加值和乘值，每個操作都可以描述成 代表把 改成 ，那麼先做 再做 就會變成 ，所以結合後的操作是 。基本的原則是「如果操作一對操作二有分配律，那麼操作一先做」，可以試試看如果定義是 ，這樣就很難將兩個操作結合起來並保持相同的表示方式。

動態開點線段樹

前面的例子中，都是「完整的開出一整棵線段樹」，但要是我們想要開一個很大的線段樹呢？

假設 很大，例如 ，我們當然不可能開出至少是 的空間。注意到我們會真正用到的節點數量其實很少，每一個操作和詢問其實都只會用到 個節點，那我們乾脆需要用到再開出這個節點就好了。

實作上通常會用指標線段樹（當然也可以偽指標），一開始只有根節點，子節點都是 nullptr，當詢問時走到不存在的節點就當作整個區間都是預設值並回傳相應的答案，操作時走到不存在的節點就開一個新節點，同樣用預設值初始化。一種好用的寫法是，讓 modify 回傳節點的指標，這樣就可以在遞迴下去時直接把那一個子節點改成回傳值。