Segment-Tree

線段樹可以用來做 的區間修改、區間查詢
只要有結合律的資訊都可以用線段樹進行維護
其主要分為 build、update、query、push、pull 等函式組成
當不需要更詳細的資訊時，可以使用懶標記來記錄大致訊息

在線段樹中儲存的編號有兩種表達形式

0-based: id2+1 / id2+2
1-based: id2 / id2+1

id 為當前線段樹節點的編號
l、r 代表當前第 id 個節點在原陣列的區間
ql、qr 代表當前查詢的區間

以下為 1-based 的範例程式碼

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
57
58
59
60
61

int n; // n 為節點數

struct Node {
    int data, tag;
    Node() : data(0), tag(0) {}
};

vector<Node> seg;

int get_val(int l, int r, int id) {
    return seg[id].data + seg[id].tag * (r-l+1);
}

void pull(int l, int r, int id) {
    int m = (l+r)>>1;
    seg[id].data = get_val(l, m, id<<1) + get_val(m+1, r, id<<1|1);
}

void push(int l, int r, int id) {
    seg[id].data += seg[id].tag * (r-l+1);
    seg[id<<1].tag += seg[id].tag;
    seg[id<<1|1].tag += seg[id].tag;
    seg[id].tag = 0;
}

void build(vector<int> &v, int l = 0, int r = n-1, int id = 1) {
    if (l == r) return void(seg[id].data = v[l]);
    int m = (l+r)>>1;
    build(v, l, m, id<<1);
    build(v, m+1, r, id<<1|1);
    seg[id].data = seg[id<<1].data + seg[id<<1|1].data;
}

void update(int ql, int qr, int v, int l = 0, int r = n-1, int id = 1) {
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) return void(seg[id].tag += v);
    push(l, r, id);
    int m = (l+r)>>1;
    update(ql, qr, v, l, m, id<<1);
    update(ql, qr, v, m+1, r, id<<1|1);
    pull(l, r, id);
}

int query(int ql, int qr, int l = 0, int r = n-1, int id = 1) {
    if (l > qr || r < ql) return 0;
    if (l >= ql && r <= qr) return get_val(l, r, id);
    push(l, r, id);
    int m = (l+r)>>1;
    return query(ql, qr, l, m, id<<1) + query(ql, qr, m+1, r, id<<1|1); 
}

signed main() {
    cin >> n;
    vector<int> v(n);
    seg.assign(n<<2|1, Node());
    for (auto &i : v) cin >> i;
    build(v);
    query(0, 3);
    update(1, 3, 5);
    query(0, 3);
}

這代表線段樹可以用來求區間和、乘積、最小最大值、最大公因數等等