47 · 线段树

第 46 节的树状数组很快，但它只吃“能相减”的信息：和、异或、计数。一旦题目要区间加并且区间求和，或者要区间最值，那套 12 行就不够了。这一节写一个通用得多的结构：把区间二分到底，每个节点维护自己那一段的整体信息。四十行代码，覆盖比赛里大半的区间问题。

先把区间怎么分钉死。这是线段树唯一不随题目变化的部分，也是 90% 的错位 bug 的来源。根节点管 [1, n]。对一个管 [l, r] 的节点，令 mid = (l + r) / 2（向下取整），把它劈成左儿子 [l, mid] 与右儿子 [mid+1, r]，两段长度差不超过 1。一直劈到 l == r，那就是叶子，管一个位置。

                      [1,5]                    节点编号 p = 1
                    /       \
              [1,3]           [4,5]                 p = 2, 3
             /     \         /     \
         [1,2]   [3,3]   [4,4]   [5,5]              p = 4, 5, 6, 7
         /   \
      [1,1] [2,2]                                   p = 8, 9

  左儿子 2p，右儿子 2p+1：堆式编号，不用存指针，也不用存区间（l、r 现场推）

编号带来一个副作用：会跳号。n = 5 时最大编号是 9，n = 6 时直接跳到 13。所以数组必须开 4n——按 2n 开会在 n = 6 这种小数据上就踩出去。这个 4 是怎么来的，数学补给里算清楚。

一个询问区间 [ql, qr] 与当前节点 [l, r] 的关系只有三种：完全包含（整段都要，直接返回，不再往下）、完全不相交（根本不会递归进来）、部分相交（两边各自递归）。query 里那几个 if，全部只是在区分这三件事。

接下来四张卡对应线段树的四块骨头：建树、合并、查询、懒标记。前两张是“从下往上”，第三张是“从上往下”，第四张解决“整段修改怎么不往下走”。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
long long a[N], s[N << 2];             // s[p]：节点 p 管辖区间内所有数的和

void pushup(int p) { s[p] = s[p << 1] + s[p << 1 | 1]; }

void build(int p, int l, int r) {
    if (l == r) { s[p] = a[l]; return; }         // 叶子：直接抄原数
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);                       // 左子树 [l, mid]
    build(p << 1 | 1, mid + 1, r);               // 右子树 [mid+1, r]
    pushup(p);                                   // 儿子都好了，才能推自己
}

int main() {
    int n = 5;
    long long b[6] = {0, 1, 5, 4, 2, 3};
    for (int i = 1; i <= n; ++i) a[i] = b[i];
    build(1, 1, n);
    cout << s[1] << "\n";                        // 1+5+4+2+3 = 15
    cout << s[2] << " " << s[3] << "\n";         // a[1..3]=10, a[4..5]=5
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

long long s[100];                        // 假设树已建好，2 是左儿子、3 是右儿子

void pushup(int p) { s[p] = s[p << 1] + s[p << 1 | 1]; }

int main() {
    s[2] = 10; s[3] = 5;                 // 左儿子 10，右儿子 5
    pushup(1);
    cout << s[1] << "\n";                // 15
    // 换成区间最大值，只改这一句：mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n = 5;
long long a[6] = {0, 1, 5, 4, 2, 3}, s[24];

void build(int p, int l, int r) {
    if (l == r) { s[p] = a[l]; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
    s[p] = s[p << 1] + s[p << 1 | 1];
}

long long query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return s[p];          // 整段被包住
    int mid = (l + r) >> 1;
    long long res = 0;
    if (ql <= mid) res += query(p << 1, l, mid, ql, qr);          // 左半边有交集
    if (qr > mid)  res += query(p << 1 | 1, mid + 1, r, ql, qr);  // 右半边有交集
    return res;
}

int main() {
    build(1, 1, n);
    cout << query(1, 1, n, 2, 4) << "\n";         // 5+4+2 = 11
    cout << query(1, 1, n, 1, 5) << "\n";         // 15
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

long long s[100], tag[100];              // 设 1 号管 [1,5]，2、3 号是它的儿子

void apply(int p, int l, int r, long long v) {
    s[p] += v * (r - l + 1);             // 和增加 v 乘元素个数
    tag[p] += v;                         // 欠账记上
}

void pushdown(int p, int l, int r) {
    if (!tag[p]) return;                 // 没欠账，走人
    int mid = (l + r) >> 1;
    apply(p << 1, l, mid, tag[p]);       // 左儿子 [l, mid] 结账
    apply(p << 1 | 1, mid + 1, r, tag[p]);   // 右儿子 [mid+1, r] 结账
    tag[p] = 0;                          // 账分完了，自己清零
}

int main() {
    s[1] = 15; s[2] = 10; s[3] = 5;      // 和分别是 15、10、5
    apply(1, 1, 5, 2);                   // [1,5] 整段加 2
    cout << s[1] << " " << s[2] << "\n"; // 25 10：儿子还没结账
    pushdown(1, 1, 5);
    cout << s[2] << " " << s[3] << "\n"; // 16 9：左段 3 个数各加 2，右段 2 个数各加 2
    return 0;
}

模板题把上面四块骨头一次串起来：区间加、区间求和。这是线段树最常见的形态，其他变体基本只是换 pushup 那一行和 query 的合并方式。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
int n, m;
ll a[N], s[N << 2], tag[N << 2];       // s：区间和；tag：还没下推的加量

void pushup(int p) { s[p] = s[p << 1] + s[p << 1 | 1]; }

void build(int p, int l, int r) {
    if (l == r) { s[p] = a[l]; return; }        // 叶子
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void apply(int p, int l, int r, ll v) {         // 给整段 [l,r] 加 v
    s[p] += v * (r - l + 1);                    // 和增加 v 乘元素个数
    tag[p] += v;                                // 记账，等以后要用儿子时再结
}

void pushdown(int p, int l, int r) {            // 把欠账分给两个儿子
    if (!tag[p]) return;                        // 没欠账，省掉一切
    int mid = (l + r) >> 1;
    apply(p << 1, l, mid, tag[p]);
    apply(p << 1 | 1, mid + 1, r, tag[p]);
    tag[p] = 0;                                 // 账已分完，自己清零
}

void update(int p, int l, int r, int ql, int qr, ll v) {
    if (ql <= l && r <= qr) { apply(p, l, r, v); return; }   // 整段被包住就停手
    pushdown(p, l, r);                          // 要进儿子了，先结账
    int mid = (l + r) >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr, v);
    if (qr > mid)  update(p << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(p);                                  // 儿子变了，自己重算
}

ll query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return s[p];        // 整段都要，直接返回
    pushdown(p, l, r);                          // 漏掉这一行，样例就会错
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid) res += query(p << 1, l, mid, ql, qr);
    if (qr > mid)  res += query(p << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);

    while (m--) {
        int op, x, y;
        ll k;
        cin >> op >> x >> y;
        if (op == 1) { cin >> k; update(1, 1, n, x, y, k); }
        else cout << query(1, 1, n, x, y) << "\n";
    }
    return 0;
}

模板题只用了“和”。真实的题目往往是别的信息，这时要改的其实只有三处：pushup 的合并方式、query 里 res 的合并方式与初值、tag 的含义与 apply 的写法。下面换一个最常见的：区间最大值，配单点修改。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
const ll NEG = -(1LL << 60);           // 最值查询的中性元：比任何答案都小
ll mx[N << 2];

void pushup(int p) { mx[p] = max(mx[p << 1], mx[p << 1 | 1]); }   // 只换这一句

void modify(int p, int l, int r, int pos, ll v) {                 // 单点赋值
    if (l == r) { mx[p] = v; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) modify(p << 1, l, mid, pos, v);
    else            modify(p << 1 | 1, mid + 1, r, pos, v);
    pushup(p);                        // 儿子变了，自己跟着变
}

ll queryMax(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mx[p];
    int mid = (l + r) >> 1;
    ll res = NEG;
    if (ql <= mid) res = max(res, queryMax(p << 1, l, mid, ql, qr));
    if (qr > mid)  res = max(res, queryMax(p << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

int main() {
    int n = 6;
    ll a[7] = {0, 3, 1, 4, 1, 5, 9};
    for (int i = 1; i <= n; ++i) modify(1, 1, n, i, a[i]);         // 逐个位置建树
    cout << queryMax(1, 1, n, 2, 4) << "\n";                       // max(1,4,1) = 4
    modify(1, 1, n, 3, 8);                                        // a[3] 改成 8
    cout << queryMax(1, 1, n, 2, 4) << "\n";                       // max(1,8,1) = 8
    return 0;
}

注意这份代码里没有 tag、没有 pushdown。因为修改是单点的，一路走到叶子，不存在“整段还没结算”的情况。单点修改的题，懒标记整套都可以删掉。反过来，只要支持区间修改，就必须有 tag；而 tag 的含义决定了 apply 怎么写：区间加是 s[p] += v*(len)、区间赋值是 s[p] = v*(len)，区间取反是 s[p] = len − s[p]。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 200005;
int cap;                              // 树的长度 = 操作总数（最多插入这么多次）
ll D, mx[N << 2];                     // 插入值都落在 [0, D)，所以 0 是安全的初值

void modify(int p, int l, int r, int pos, ll v) {        // 单点赋值
    if (l == r) { mx[p] = v; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) modify(p << 1, l, mid, pos, v);
    else            modify(p << 1 | 1, mid + 1, r, pos, v);
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);             // 儿子变了，自己跟着变
}

ll queryMax(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mx[p];                // 整段被包住
    int mid = (l + r) >> 1;
    ll res = 0;                                          // 非负数，用 0 当"没有"
    if (ql <= mid) res = max(res, queryMax(p << 1, l, mid, ql, qr));
    if (qr > mid)  res = max(res, queryMax(p << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m >> D;
    cap = m;                                         // 最多插 m 次，树不用更长
    int tail = 0;                                    // 当前数列长度
    ll t = 0;

    while (m--) {
        char op;
        ll n;
        cin >> op >> n;
        if (op == 'A') {
            ll v = ((n + t) % D + D) % D;             // 先加 t，再取模，负数也落进 [0,D)
            modify(1, 1, cap, ++tail, v);             // 追加到最后一个位置
        } else {
            int L = (int)n;
            t = queryMax(1, 1, cap, tail - L + 1, tail);   // 最后 L 个
            cout << t << "\n";
        }
    }
    return 0;
}