实战：线段树（区间查询+区间更新）

线段树，说实话，是很多C++选手的「噩梦」。

我第一次接触它是在大学算法课上，当时觉得这玩意儿不就是个二叉树吗？有什么难的。结果自己手写的时候，边界条件、懒标记、递归深度……各种问题接踵而至。后来在项目中做区间统计功能，才真正体会到它的威力。

今天我们就来彻底搞懂它。

什么是线段树？

线段树是一种二叉树结构，专门用来处理数组的区间问题。比如你有一个长度为N的数组，需要频繁做两件事：

• 区间查询：求某个区间 [L, R] 的和、最大值、最小值等
• 区间更新：把某个区间 [L, R] 的所有元素都加上一个值

如果用普通数组，更新是O(1)，但查询是O(N)。如果数据量一大，比如10万次操作，直接卡死。

线段树能把这两个操作都优化到 O(log N)。怎么做到的？说白了就是「分而治之」——把大区间不断对半切，直到每个叶子节点代表一个元素。

线段树的结构

我习惯用数组来模拟二叉树。根节点下标为1，左孩子是2*i，右孩子是2*i+1。这样不需要指针，内存连续，访问速度快。

假设数组长度为N，线段树需要开多大？

• 最坏情况：N是2的幂，树高为 log₂N，节点数约 2N
• 一般情况：开 4*N 绝对安全

嗯，这里要注意：一定要开4倍空间。我曾经因为只开了2倍，在边界测试时数组越界，排查了半天才发现是空间不够。

懒标记（Lazy Propagation）

区间更新如果不做优化，每次都要更新到叶子节点，那复杂度又回到O(N)了。

懒标记的思路很简单：先欠着，等查询的时候再还。

具体来说：

• 更新一个区间时，如果当前节点完全被覆盖，就只更新这个节点的值，并打上一个「懒标记」
• 下次访问这个节点时，先把懒标记下传给子节点，再继续操作

这样做的好处是：更新操作只影响O(log N)个节点，而不是全部叶子。

代码实现

下面我给出一个完整的线段树实现，支持区间加法和区间求和。代码里我加了详细的注释，方便你理解。

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

const int MAXN = 100005;
int a[MAXN];          // 原始数组
long long tree[4 * MAXN];  // 线段树
long long lazy[4 * MAXN];  // 懒标记

// 建树
void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

// 下传懒标记
void push_down(int node, int l, int r) {
    if (lazy[node] != 0) {
        int mid = (l + r) / 2;
        // 更新左孩子
        tree[node * 2] += lazy[node] * (mid - l + 1);
        lazy[node * 2] += lazy[node];
        // 更新右孩子
        tree[node * 2 + 1] += lazy[node] * (r - mid);
        lazy[node * 2 + 1] += lazy[node];
        // 清除当前节点懒标记
        lazy[node] = 0;
    }
}

// 区间更新：[L, R] 加上 val
void update(int node, int l, int r, int L, int R, long long val) {
    if (L <= l && r <= R) {
        tree[node] += val * (r - l + 1);
        lazy[node] += val;
        return;
    }
    push_down(node, l, r);
    int mid = (l + r) / 2;
    if (L <= mid) update(node * 2, l, mid, L, R, val);
    if (R > mid) update(node * 2 + 1, mid + 1, r, L, R, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

// 区间查询：[L, R] 的和
long long query(int node, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[node];
    }
    push_down(node, l, r);
    int mid = (l + r) / 2;
    long long res = 0;
    if (L <= mid) res += query(node * 2, l, mid, L, R);
    if (R > mid) res += query(node * 2 + 1, mid + 1, r, L, R);
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, L, R;
        cin >> op >> L >> R;
        if (op == 1) {
            long long val;
            cin >> val;
            update(1, 1, n, L, R, val);
        } else {
            cout << query(1, 1, n, L, R) << endl;
        }
    }
    return 0;
}

核心逻辑流程图

下面我用一张SVG图来展示线段树区间更新的核心流程。你仔细看，懒标记的传递路径非常清晰。

避坑指南

我曾经在写线段树时踩过不少坑，这里列几个最常见的：

复杂度分析

操作	时间复杂度	空间复杂度
建树	O(N)	O(4N)
区间查询	O(log N)	O(1) 额外
区间更新	O(log N)	O(1) 额外

你想想看，如果N=100000，普通数组做10万次区间更新+查询，复杂度是O(N²)，根本跑不动。而线段树只需要O(N log N)，差距是数量级的。

总结

线段树的核心就两件事：分治 + 懒标记。

• 分治让查询和更新都只走一条路径，复杂度降到log级别
• 懒标记让区间更新不用动所有叶子，效率大幅提升

我个人建议你先把上面的代码手敲一遍，跑几个测试用例。然后试着改成求最大值、最小值，或者支持区间赋值操作。等你把代码改熟了，线段树就不再是噩梦，而是你的利器。