线段树是一种基于分治思想的二叉树结构，用于在区间上进行信息统计。

概念

线段树的性质：

  1. 每个节点代表一个区间
  2. 具有唯一的根节点，代表整个区间的统计范围，如 $[1, N]$。
  3. 每个页节点代表长度为1的元区间 $[x, x]$。
  4. 每个非叶子节点若其代表的区间是 $[l, r]$，则其左子节点是 $[l, mid]$，右子节点是 $[mid+1, r]$，其中 $mid = (l+r)/2$ (向下取证)。
  5. 编号：根节点编号编号为1，编号为 $x$ 的左子节点编号为 $x*2$，右子节点编号为 $x*2+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
46
// 构建一棵用于保存区间最值的线段树
struct segmentTree {
    int l, r;
   	int dat;
} t[SIZE*4];

void build(int p, int l, int r) {
    t[p].l = l;
    t[p].r = r;
    if (l == r) {
        t[p].dat = b[l];
        return;
    }

    int mid = l + (r-l)/2;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);

    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

// 单点修改
void change(int p, int x, int v) {
    if (t[p].l == t[p].r) {
        t[p].dat = v;
        return;
    }
  	
  	// 向下更新
    int mid = t[p].l + (t[p].r - t[p].l)/2;
    if (x <= mid) change(p*2, x, d);
    else          change(p*2+1, x, d);
		
  	// 回溯更新
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

// 在跟节点为p的子树中查找区间[l, r]的
int ask(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].dat;
  	int mid = t[p].l + (t[p].r - t[p].l)/2;
		int val = -(1<<30);
  	if (l <= mid) val = max(val, ask(p*2, l, r));
  	if (r > mid)  val = max(val, ask(p*2+1, l, r));
    return val;
}

延迟标记的线段树

在面对区间增加的情况，可以采用带有延迟标记的线段树。带有延迟标记的节点是已经“增加了”但其“子节点没有增加”的节点。

待补充

扫描线与线段树

待补充