1. 认识线段树

1.1. 线段树的概念

线段树是一种主要用于维护区间信息的数据结构。主要用于单点修改、单点查询、区间修改、区间查询。

线段树单次操作时间复杂度为 O(\log n)。

1.2. 线段树的基本思想

线段树的基本思想是将区间二分分段，构成一棵树，直至叶子节点所代表的区间只有一个元素为止。例如，将区间 [1,3] 分割成区间 [1,2] 和区间 [3,3]。此时区间 [1,2] 还并非只有一个元素，再分成区间 [1,1] 和区间 [2,2]，即为分割成的线段树。

1.3. 线段树的性质

线段树有如下的性质：

• 对于每个节点，要么没有子节点（即叶子结点），要么有两个子节点；
• 长度为 n 的序列，建立的线段树有 2n-1 个节点；
• 线段树的高度为 \lceil \log n \rceil。

线段树维护的信息必须具有可合并性，即更大区间的信息可以通过小区间合并得到。

2. 基础的线段树

例题：洛谷 P3372

2.1. 建树

定义如下的结构体和数组作为节点：

struct node {
    int l, r, sum;
} t[N << 2];

注意这里数组要开成 4 倍大小：用数组存树，父节点编号为 i，左子节点编号为 2i，右子节点编号为 2i+1，线段树有 2n-1 个节点，最大节点编号不超过 2 \times (2n-1) + 1 = 4n-1。的所以只需要开 4 倍空间就可以了。

采用递归的方式建立线段树，如果 l = r，说明这个节点是叶子节点，否则，将区间进一步拆分，分为左子节点和右子节点，然后再将区间信息合并（一般称为 pushup）。代码如下：

void pushup(int u) {
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
    if (l == r) t[u] = {l, r, a[l]}; // 叶子结点
    else {
        t[u].l = l, t[u].r = r;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

build(1, 1, n);

2.2. 区间修改和查询

要修改某一区间 [l, r]，实际上就是要修改所有完全包含在 [l, r] 中的线段树上的区间的值。考虑下面一个问题：如何在不专门修改一个区间的子区间的记录值的情况下，修改整个区间的记录值，同时保证区间和子区间的记录都正确、

为此，我们引入懒标记（lazy tag）的概念。具体来说，在修改当前区间的值时，懒标记将原本要下放到子区间的变化存储起来，在适当的时候再下传（pushdown），即下放到子区间。于是，我们首先写出 maketag 函数和 pushdown 函数：

void maketag(int u, int len, ll x) {
    tag[u] += x;
    t[u] += x * len;
}

void pushdown(int u, int l, int r) {
    int mid = l + r >> 1;
    maketag(u << 1, mid - l + 1, tag[u]);
    maketag(u << 1 | 1, r - mid, tag[u]);
    tag[u] = 0;
}

这里注意，在打懒标记的时候，要修改当前区间的记录值。下传懒标记之后，要将当前区间的懒标记清空，以避免重复统计。

接下来，我们要对区间进行修改。像前面说的，要修改某一区间 [l, r]，实际上就是要修改所有完全包含在 [l, r] 中的线段树上的区间的值。那么，如果一个节点代表的区间完全被包含在 [l, r] 中，我们可以直接对这个区间打标记修改；如果这个区间与 [l, r] 有重合，就要再对这个区间进行分割，直到区间被 [l, r] 完全包含。在这个过程中，我们先下传区间懒标记信息，更新子区间信息后在汇总信息。代码如下：

void update(int u, int L, int R, int l, int r, ll x) {
    if (l <= L && R <= r) maketag(u, R-L+1, x);
    else if (l <= R && r >= L) {
        int mid = L + R >> 1;
        pushdown(u, L, R);
        update(u<<1, L, mid, l, r, x);
        update(u<<1|1, mid+1, R, l, r, x);
        pushup(u);
    }
}

区间查询也是同理，注意查询子区间前要下传懒标记，否则子区间数据不正确。代码如下：

ll query(int u, int L, int R, int l, int r) {
    if (l <= L && R <= r) return t[u];
    else if (L > r || R < l) return 0;
    else {
        int mid = L + R >> 1;
        pushdown(u, L, R);
        return query(u<<1, L, mid, l, r) + query(u<<1|1, mid+1, R, l, r);
    }
}

至此，我们便完成了单懒标记线段树的操作的实现。

3. 多懒标记线段树

3.1. 乘法和加法的处理

例题：洛谷 P3373

考虑采用乘法和加法两个懒标记，我们可以为相关函数添加 type 参数来区分乘法和加法操作。考虑下面的问题：在下传时，应该先下传乘法，还是先下传加法？

假定一个区间原来的记录值是 t，考虑下面两种情况：先乘 x，再加 y，此时记录值应该变更为 xt + y，注意到此时两个标记互不产生影响；先加 x，后乘 y，此时记录值应该变更为 (t + x)y，即 xt + xy，注意到此时，乘法标记 y 对加法标记 x 产生了影响。

因此，我们在修改乘法标记时，需要同步修改加法标记；同时，在下传标记时，我们要先下传乘法标记，再下传加法标记。有了以上思路，这道题代码只需在上面的基础上稍作修改即可。这里不再给出。注意本体要求模去一个大数，要在加和乘的时候做处理，防止数据溢出。

3.2. 赋值和加法的处理

例题：洛谷 P1253

在这道题中，要求区间最大值。考虑最大值这一操作具有可合并性。并且有两个操作：赋值和加法，因此我们需要使用两个懒标记。考虑：在赋值时，原本的加法懒标记都会失效；在加法时，如果已经有赋值懒标记了，那么加法会作用在赋值懒标记的基础上。也就是说，如果当前操作是赋值，就直接修改赋值标记并将加法标记清空；如果当前操作时加法，考虑两种情况：如果当前赋值标记不为空，在赋值标记上做加法，否则在加法标记上做加法。由于有可能赋值为 0，因此赋值标记为空时应当用一个极大值进行标记（如 INT_MAX、0x3f3f3f3f）。将 maketag 和 pushdown 函数修改如下：

void maketag(int u, ll x, int type) {
    if (type == 1) { // 赋值操作
        tag_add[u] = 0, tag_set[u] = x, t[u] = x;
    }
    else { // 加法操作
        if (tag_set[u] == INF) tag_add[u] += x;
        else tag_set[u] += x;
        t[u] += x;
    }
}

void pushdown(int u) {
    if (tag_set[u] == INF) {
        maketag(u<<1, tag_add[u], 2);
        maketag(u<<1|1, tag_add[u], 2);
        tag_add[u] = 0;
    }
    else {
        maketag(u<<1, tag_set[u], 1);
        maketag(u<<1|1, tag_set[u], 1);
        tag_set[u] = INF;
    }
}

4. 总结

在算法竞赛中，线段树是一种非常有用的数据结构，可以用于维护区间可合并信息（如加和、最大值等）。有效利用线段树，是算法水平进阶的一个重要能力。