线段树：区间查询、单点修改与懒标记

以前看到“线段树：区间查询、单点修改与懒标记”，我会下意识去找一份模板保存下来。后来发现这样学得很快，忘得也快，因为线段树的数组通常开四倍、递归参数又很多，我最初一直在背代码，没有先看清每个节点保存的是哪一段区间。所以这篇不从标准答案起步，而是顺着我当时的疑问一点点往下拆。

线段树解决的是“区间问题动态变化”的场景。如果数组不变，只做区间查询，前缀和就够了；如果要频繁修改元素或区间，再频繁查询区间结果，线段树就有价值。

它从哪里来

线段树随着计算几何和区间查询问题的发展而普及。它把一个大区间递归拆成若干可复用的小区间，让“每次都重新扫描整个范围”变成沿树访问少量节点。后来懒标记又解决了批量区间更新。

线段树解决什么问题

线段树区间分解

图：查询区间可以被拆成几个线段树节点，而不是扫描全部元素

线段树适合维护满足可合并特性的区间信息：

区间和。
区间最小值。
区间最大值。
区间最大公约数。
区间覆盖状态。

关键是两个子区间的答案能合并成父区间答案。

建树

下面以区间和为例。

class SegmentTree {
    private final int[] tree;
    private final int n;

    SegmentTree(int[] nums) {
        this.n = nums.length;
        this.tree = new int[n * 4];
        build(nums, 1, 0, n - 1);
    }

    private void build(int[] nums, int node, int left, int right) {
        if (left == right) {
            tree[node] = nums[left];
            return;
        }
        int mid = left + (right - left) / 2;
        build(nums, node * 2, left, mid);
        build(nums, node * 2 + 1, mid + 1, right);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

数组开 4n 是常见写法，简单稳妥，不用纠结精确节点数。

区间查询

int query(int ql, int qr) {
    return query(1, 0, n - 1, ql, qr);
}

private int query(int node, int left, int right, int ql, int qr) {
    if (ql <= left && right <= qr) {
        return tree[node];
    }
    int mid = left + (right - left) / 2;
    int ans = 0;
    if (ql <= mid) ans += query(node * 2, left, mid, ql, qr);
    if (qr > mid) ans += query(node * 2 + 1, mid + 1, right, ql, qr);
    return ans;
}

查询时只访问与目标区间相交的节点，复杂度通常是 O(log n)。

单点修改

void update(int index, int value) {
    update(1, 0, n - 1, index, value);
}

private void update(int node, int left, int right, int index, int value) {
    if (left == right) {
        tree[node] = value;
        return;
    }
    int mid = left + (right - left) / 2;
    if (index <= mid) {
        update(node * 2, left, mid, index, value);
    } else {
        update(node * 2 + 1, mid + 1, right, index, value);
    }
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

修改一个叶子后，需要一路向上重算父节点。

懒标记

如果要做区间修改，比如把 [l, r] 全部加 3，不能每个元素都改。懒标记的思想是：当前节点覆盖的区间已经整体更新，但它的子节点先不急着更新，等真正访问子节点时再下推。

懒标记适合区间更新 + 区间查询，但代码复杂度明显更高。学习顺序建议是：先掌握无懒标记的线段树，再学懒标记。

我的分析

线段树的难点不是代码长，而是区间边界。每个节点都代表 [left, right]，查询区间是 [ql, qr]。只要这两个区间关系清楚，代码就不会乱。

工程里，线段树适合排行榜区间统计、时间段指标查询、动态区间聚合、游戏地图范围状态等场景。但如果只是静态查询，前缀和更简单。

面试题

线段树为什么能把区间查询降到 O(log n)？
什么样的区间信息可以用线段树维护？
线段树数组为什么常开 4n？
懒标记解决什么问题？
前缀和、树状数组、线段树分别适合什么场景？