Segment Tree

MrHe··5 min read

好久没更新了，今天咱们来聊聊一个面试中的常客，也是一个能把很多复杂问题变简单的神器——线段树（Segment Tree）。

别一听到“树”就头大，这东西说白了就是个“高级版的分块数组”，核心思想就是“预处理”和“分治”。咱们的目标是，通过这篇文章，让你不仅能手撕线段树，还能理解它背后的思维方式，这样以后遇到类似的区间问题，脑子里能立马浮现出这个结构。

场景引入：从最笨的方法开始

老规矩，先看题。给你一个数组 arr，现在有两个操作：

  1. 把 arr[i] 的值更新成 v。

  2. 查询 arr 数组在 [L...R] 范围上的累加和是多少。

这两个操作会非常频繁。你怎么搞？

解法一：无脑暴力法

这是我看到问题后，脑子里第一个蹦出来的想法，也是最直观的方法。

  • 查询 [L...R] 的和：写个 for 循环，从 L 遍历到 R，一个个加起来。时间复杂度 O(N)。

  • 更新 arr[i]：直接 arr[i] = v。时间复杂度 O(1)。

这个方法简单吧？但问题在哪？如果查询操作特别多，比如来个十万次查询，每次都 O(N) 走一遍，那服务器就直接冒烟了。这个方法在查询频繁的场景下，性能太差。

那反过来想，能不能让查询变快？

解法二：前缀和数组

为了让查询变快，我们可以预处理一个 sum 数组，sum[i] 表示 arr[0...i] 的累加和。

  • 查询 [L...R] 的和：sum[R] - sum[L-1] (注意 L=0 的边界)。时间复杂度 O(1)，爽！

  • 更新 arr[i]：问题来了。如果我更新了 arr[i]，那么 sum[i]、sum[i+1]、sum[i+2]... 一直到数组末尾的所有值，都得跟着变。更新一个点，最差要动整个后缀。时间复杂度 O(N)。

你看，暴力法是查询慢、更新快；前缀和是查询快、更新慢。有没有一种方法，能让它俩都别太慢，均衡一下呢？

这，就是线段树登场的时刻。它的目标就是把查询和更新的时间复杂度都降到 O(logN)。

解法三：线段树，空间换时间的艺术

我们是怎么想到线段树的？

你看，暴力查询慢，是因为每次都重复计算了很多区间的和。前缀和更新慢，是因为一个点的变动会“级联”影响后面的所有预处理结果。

线段树的核心思路就是：把整个数组的区间，像切蛋糕一样，一块块切分，然后用一棵树来管理这些“蛋糕块”的信息。

每个节点，都代表原数组里的一个区间 [L...R] 的信息（比如累加和）。

  • 一个父节点 [L...R]，它的左孩子就代表 [L...M]，右孩子代表 [M+1...R]，其中 M 是 (L+R)/2。

  • 一直切分下去，直到 L==R，这时候就到了叶子节点，它代表的就是数组里的一个单独的元素 arr[L]。

比如数组 [1, 3, 5, 7, 9, 11]，它对应的线段树（存累加和）大概长这样：

看明白这个结构，代码实现就水到渠成了。我们需要实现三个核心功能：build（建树）、update（单点更新）、query（区间查询）。

1. 建树 (Build)

就是把上面那个图用代码构造出来。我们通常用一个数组来模拟这棵树。如果父节点的下标是 i，那它的左孩子就是 2*i，右孩子是 2*i+1（为了方便，我们从下标 1 开始用）。

为啥用数组？因为线段树是一棵近似的完全二叉树，用数组存不浪费空间，而且寻址方便。数组开多大？经验值是 4*N，足够用了，懒得去精确计算。

// arr 是原始数组
// tree 是我们的线段树数组
// node 是当前节点在 tree 数组中的下标
// start, end 是这个节点代表的区间 [start...end]
void build(int[] arr, int[] tree, int node, int start, int end) {
    if (start == end) {
        // 叶子节点，存单个元素的值
        tree[node] = arr[start];
        return;
    }

    int mid = start + (end - start) / 2;
    int leftNode = 2 * node;
    int rightNode = 2 * node + 1;

    // 递归去建左右子树
    build(arr, tree, leftNode, start, mid);
    build(arr, tree, rightNode, mid + 1, end);

    // 建完左右子树后，回溯时，用子节点的信息更新父节点
    // 这叫 Post-order Traversal 的思想，也叫 PushUp
    tree[node] = tree[leftNode] + tree[rightNode];
}

build 的过程，每个元素只被访问一次，所以复杂度是 O(N)。

2. 单点更新 (Update)

比如我要把 arr[3] 的值改成 6。在线段树里怎么走？

从根节点出发，arr[3] 在 [0...5] 区间里。mid 是 2，所以 3 在右半部分 [3...5]，我们就往右子树走。到了代表 [3...5] 的节点，mid 是 4，3 在左半部分 [3...4]，我们继续往左子树走......直到找到代表 [3...3] 的叶子节点，把它更新掉。

更新完叶子节点还没完！它的父节点、爷爷节点...一直到根节点，它们存的累加和都得跟着变。所以，我们在递归返回的时候，要一路 pushUp，重新计算父节点的和。

// idx 是要更新的数组下标，val 是新的值
void update(int[] tree, int node, int start, int end, int idx, int val) {
    if (start == end) {
        // 找到叶子节点了
        tree[node] = val;
        return;
    }

    int mid = start + (end - start) / 2;
    int leftNode = 2 * node;
    int rightNode = 2 * node + 1;

    // 判断去左边还是右边找
    if (idx >= start && idx <= mid) {
        update(tree, leftNode, start, mid, idx, val);
    } else {
        update(tree, rightNode, mid + 1, end, idx, val);
    }

    // 孩子变了，爹也得跟着变
    tree[node] = tree[leftNode] + tree[rightNode];
}

这个过程就是从根节点走到一个叶子节点，深度是 logN，所以时间复杂度是 O(logN)。

3. 区间查询 (Query)

这是线段树最精髓的地方。比如我要查询 [2...5] 的和。

还是从根节点 [0...5] 开始。我们的查询区间 [2...5] 和当前节点区间 [0...5] 有交集，但没完全覆盖。咋办？

那就把任务分解给左右孩子。

  • 左孩子管 [0...2]，右孩子管 [3...5]。

  • 查询任务 [2...5] 扔给左孩子，它发现 [2...5] 和 [0...2] 的交集是 [2...2]。

  • 查询任务 [2...5] 扔给右孩子，它发现 [2...5] 和 [3...5] 的交集是 [3...5]。

继续往下：

  • 对于任务 [2...2]: 节点 [0...2] 继续分裂，最后会找到代表 [2...2] 的叶子节点，直接返回它的值。

  • 对于任务 [3...5]: 节点 [3...5] 被查询区间 [2...5] 完全覆盖！ 这时候就体现出优势了：我不需要再往下走了！ 直接返回这个节点预存好的 [3...5] 的总和就行了。

这就是线段树查询快的核心：用 O(1) 的时间，获取一整个大区间的聚合信息，避免了不必要的深入递归。

// [L...R] 是我们要查询的区间
int query(int[] tree, int node, int start, int end, int L, int R) {
    // case 1: 当前区间和查询区间没交集，贡献是0
    if (R < start || L > end) {
        return 0;
    }

    // case 2: 当前区间被查询区间完全包含，直接返回当前节点的值
    if (L <= start && end <= R) {
        return tree[node];
    }

    // case 3: 部分重叠，任务分解给左右孩子
    int mid = start + (end - start) / 2;
    int leftNode = 2 * node;
    int rightNode = 2 * node + 1;

    int p1 = query(tree, leftNode, start, mid, L, R);
    int p2 = query(tree, rightNode, mid + 1, end, L, R);

    return p1 + p2;
}

可以证明，每次查询，最多把区间拆分成 logN 级别的块，所以时间复杂度是 O(logN)。

进阶：懒加载 (Lazy Propagation)

上面的解法三已经很优秀了，但它只解决了“单点更新”。如果题目变成“给区间 [L...R] 上的每个数都加上 v”呢？

你可能会说，简单，循环 L 到 R，一个个调用 update 方法不就行了？ 那复杂度就变成了 (R-L+1) * logN，最坏是 O(N*logN)，又回去了。

懒加载就是为了解决这个问题的。它的思想更“懒”了：

当一个更新任务要覆盖一个节点的整个区间时，我先不把这个更新真正地执行下去，而是打个“懒标记” (lazy tag) 在这个节点上，告诉它：“喂，你的地盘上所有元素都要加 v 啊，记一下，回头再说。” 然后直接返回。

什么时候“再说”呢？

当下一次有查询或者更新任务，需要经过这个带标记的节点，并且需要把它分裂开的时候，它才不得不把之前欠的“债”（懒标记）还给它的左右孩子。这个过程叫 pushDown。

我们给每个节点增加一个 lazy 字段。

pushDown 过程是这样的：

  1. 把当前节点的 lazy 值下发给左右孩子。

  2. 更新左右孩子的 sum 值（因为它们也受到了懒标记的影响）。

  3. 清空当前节点的 lazy 值。

有了这个机制，我们的区间更新 rangeUpdate 和查询 query 逻辑就要稍微改动一下：

  • 在 rangeUpdate 和 query 中，每当要访问一个节点的子节点之前，必须先 pushDown 当前节点的 lazy 标记，确保子节点的信息是最新的。

代码会稍微复杂一点，但核心思想没变。

// 这是一个简化的带 Lazy Tag 的线gaishu
class SegTreeWithLazy {
    private int[] tree;
    private int[] lazy;
    private int[] arr;
    private int n;

    // ... 构造函数等 ...

    // 把当前节点的懒标记下推给孩子
    private void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            // 更新当前节点的 tree 值
            // 注意：这里是在 pushDown 的时候才真正更新 tree 值
            // tree[node] += lazy[node] * (end - start + 1);

            if (start != end) { // 如果不是叶子节点
                int leftNode = 2 * node;
                int rightNode = 2 * node + 1;
                // 把懒标记传给孩子
                lazy[leftNode] += lazy[node];
                lazy[rightNode] += lazy[node];

                // 根据懒标记，预更新孩子节点的 tree 值
                // 这样下次查询到孩子节点时，即使不 pushDown，值也是对的
                int mid = start + (end - start) / 2;
                tree[leftNode] += lazy[node] * (mid - start + 1);
                tree[rightNode] += lazy[node] * (end - (mid + 1) + 1);
            }
            // 清除当前节点的懒标记
            lazy[node] = 0;
        }
    }

    // 区间更新
    public void update(int node, int start, int end, int L, int R, int val) {
        // 先把之前欠的债还了
        // pushDown(node, start, end); // 实际上，在懒加载的更新逻辑里，这一步可以优化掉

        // 如果当前区间被完全覆盖
        if (L <= start && end <= R) {
            lazy[node] += val;
            tree[node] += val * (end - start + 1);
            return;
        }

        // 分裂前，先下推懒标记
        pushDown(node, start, end);

        int mid = start + (end - start) / 2;
        if (L <= mid) {
            update(2 * node, start, mid, L, R, val);
        }
        if (R > mid) {
            update(2 * node + 1, mid + 1, end, L, R, val);
        }

        // 记得 pushUp
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    // 区间查询
    public int query(int node, int start, int end, int L, int R) {
        if (R < start || L > end) {
            return 0;
        }

        // 如果当前区间被完全覆盖，直接返回
        if (L <= start && end <= R) {
            return tree[node];
        }

        // 查询前，必须先下推懒标记，保证孩子的信息是最新的
        pushDown(node, start, end);

        int mid = start + (end - start) / 2;
        int p1 = 0, p2 = 0;
        if (L <= mid) {
             p1 = query(2 * node, start, mid, L, R);
        }
        if (R > mid) {
             p2 = query(2 * node + 1, mid + 1, end, L, R);
        }

        return p1 + p2;
    }
}

引入懒加载后，区间更新的复杂度也降到了 O(logN)。至此，线段树就成了一个处理区间问题的完全体。

总结一下

  1. 暴力法：直观，但性能差，是优化的起点。

  2. 标准线段树：利用分治思想，将区间问题用树形结构管理。通过预处理，将单点更新和区间查询都优化到 O(logN)。核心是空间换时间。

  3. 带懒加载的线段树：在标准线段树基础上，增加“懒标记”，解决了区间更新的效率问题，使其复杂度也达到 O(logN)。核心思想是“延迟计算”。

线段树能做的远不止求和，像区间的最大/最小值、区间乘积、区间异或和等等，只要是满足结合律的操作，都可以往线段树这个框架里套。

  • #segment-tree