线段树：区间查询与动态更新

线段树：区间查询与动态更新

线段树是算法竞赛和工程实践中处理区间问题的利器。它能在 O(log n) 时间内完成区间查询与单点/区间更新，远比朴素遍历高效。本文将带你从零开始，彻底掌握线段树的核心思想与代码实现。

1. 为什么需要线段树？

设想一个场景：有一个长度为 n 的数组 arr，需要频繁进行两种操作：

• 查询：询问区间 [L, R] 内所有元素的和（或最大值/最小值）
• 更新：修改某个位置的值，或将某个区间的值全部增加 k

若使用原数组直接操作：

• 查询 O(n)，更新 O(1)，总体效率低下。
• 若使用前缀和优化查询到 O(1)，但更新又会退化为 O(n)。

线段树将两者平衡至 O(log n)，非常适合数据动态变化的区间统计场景。

2. 线段树的基本结构

线段树是一种二叉树，每个节点代表一个区间。

• 根节点：代表整个数组区间 [0, n-1]（或 [1, n]）。
• 叶节点：代表单个元素区间 [i, i]。
• 内部节点：将其区间从中间 mid 划分为左右两半，左子节点表示 [L, mid]，右子节点表示 [mid+1, R]。

每个节点存储它所管辖区间的聚合信息（例如区间和、最小值、最大值、最大公约数等）。这种分治结构保证了树的高度为 O(log n)。

图示：区间 [0,4] 的线段树，节点内数字代表区间和

3. 线段树的存储方式

通常使用数组来存储线段树，以避免指针开销。对于大小为 n 的数组，线段树最多需要 4 * n 个节点空间。

• 根节点放在下标 1 的位置（方便计算子节点）。
• 对于任意节点 p，左子节点为 p*2，右子节点为 p*2+1。

# 示例：初始化存储数组（仅示意，实际大小需根据 n 调整）
tree = [0] * (4 * n)

4. 构建线段树：build 函数

构建过程采用自底向上的递归分治。函数 build(p, l, r) 表示当前节点 p 代表区间 [l, r]，按如下步骤执行：

1. 若 l == r，则为叶子节点，直接存储原数组 arr[l] 的值。
2. 否则计算 mid = (l + r) // 2，递归构建左子树 build(p*2, l, mid) 和右子树 build(p*2+1, mid+1, r)。
3. 合并左右子树信息给节点 p，例如区间和：tree[p] = tree[p*2] + tree[p*2+1]。

时间复杂度：O(n)。

代码示例（Python，以区间求和为例）

arr = [0, 1, 3, 5, 7, 9, 11]  # 下标从1开始便于理解
n = len(arr) - 1
tree = [0] * (4 * n)

def build(p, l, r):
    if l == r:
        tree[p] = arr[l]
        return
    mid = (l + r) // 2
    build(p * 2, l, mid)
    build(p * 2 + 1, mid + 1, r)
    tree[p] = tree[p * 2] + tree[p * 2 + 1]

build(1, 1, n)  # 根节点下标1，区间[1, n]

5. 区间查询（Range Query）

查询区间 [ql, qr] 的聚合值。从根节点开始递归：

• 若当前节点区间 [l, r] 完全包含在 [ql, qr] 中，直接返回该节点存储的值。
• 若当前区间与查询区间无交集，返回一个不影响结果的“零值”（如求和返回0，求最大值返回负无穷）。
• 否则部分重叠，向左右子节点递归查询，并合并结果。

每次查询最多访问 O(log n) 个节点，因为每层最多有4个节点会被递归进入（相邻区间的边界效应）。

区间求和查询代码

def query(p, l, r, ql, qr):
    if ql <= l and r <= qr:          # 完全包含
        return tree[p]
    if qr < l or r < ql:             # 无交集
        return 0
    mid = (l + r) // 2
    left_sum = query(p * 2, l, mid, ql, qr)
    right_sum = query(p * 2 + 1, mid + 1, r, ql, qr)
    return left_sum + right_sum

6. 单点更新（Point Update）

修改原数组某个位置 idx 的值。递归找到对应的叶子节点，更新其值，然后回溯时重新计算所有祖先节点的聚合信息。

def update_point(p, l, r, idx, val):
    if l == r:                        # 叶子节点
        tree[p] = val
        return
    mid = (l + r) // 2
    if idx <= mid:
        update_point(p * 2, l, mid, idx, val)
    else:
        update_point(p * 2 + 1, mid + 1, r, idx, val)
    tree[p] = tree[p * 2] + tree[p * 2 + 1]   # 回溯更新

时间复杂度：O(log n)。

7. 区间更新与懒惰标记（Lazy Propagation）

若要给区间 [ul, ur] 的每个元素都加上 val，单点更新的方式需要 O(n log n)，无法接受。懒惰标记（Lazy Tag） 是线段树处理区间更新的核心技巧。

核心思想：延迟生效，用到再传。

• 为每个节点增加一个 lazy 标记，表示该节点代表的区间尚未下传到子节点的更新值。
• 当更新操作遇到一个节点区间完全被 [ul, ur] 覆盖时：
  1. 更新该节点的 tree 值（例如，若是区间加，则 tree[p] += (r - l + 1) * val）。
  2. 将 val 累加到该节点的 lazy 标记上，然后立即返回，不再向下递归。
• 在后续查询或更新过程中，如果访问到一个节点且它的 lazy 标记非空，则需要将更新下推给左右子节点（即 push_down 操作），并清除当前标记。

带懒惰标记的完整结构（区间加，区间求和）

tree = [0] * (4 * n)
lazy = [0] * (4 * n)

def push_down(p, l, r):
    if lazy[p] != 0:
        mid = (l + r) // 2
        # 传递给左子
        tree[p * 2] += lazy[p] * (mid - l + 1)
        lazy[p * 2] += lazy[p]
        # 传递给右子
        tree[p * 2 + 1] += lazy[p] * (r - mid)
        lazy[p * 2 + 1] += lazy[p]
        # 清除当前标记
        lazy[p] = 0

def update_range(p, l, r, ul, ur, val):
    if ul <= l and r <= ur:          # 完全覆盖
        tree[p] += val * (r - l + 1)
        lazy[p] += val
        return
    push_down(p, l, r)               # 下推标记
    mid = (l + r) // 2
    if ul <= mid:
        update_range(p * 2, l, mid, ul, ur, val)
    if ur > mid:
        update_range(p * 2 + 1, mid + 1, r, ul, ur, val)
    tree[p] = tree[p * 2] + tree[p * 2 + 1]

def query_range(p, l, r, ql, qr):
    if ql <= l and r <= qr:
        return tree[p]
    push_down(p, l, r)               # 查询前也要下推
    mid = (l + r) // 2
    res = 0
    if ql <= mid:
        res += query_range(p * 2, l, mid, ql, qr)
    if qr > mid:
        res += query_range(p * 2 + 1, mid + 1, r, ql, qr)
    return res

注意：在 update_range 和 query_range 中访问子节点之前必须调用 push_down，以保证子节点拿到最新的值。

8. 线段树的常见变体与应用

• 动态开点线段树：当值域范围极大（如 1e9）时，只创建访问过的节点，节省空间。
• 权值线段树：维护值域内各元素的出现次数，可解决全局第 k 小、前驱/后继等问题。
• 可持久化线段树（主席树）：查询历史版本，用于区间第 k 小等经典问题。
• 线段树优化 DP：利用线段树快速转移状态。

9. 注意事项与边界处理

• 数组大小：常规线段树开 4*n 基本安全；若涉及区间操作务必检查左右区间划分避免死循环。
• 下标习惯：强烈建议统一使用 1-indexed 或 0-indexed，笔者的示例代码采用 1-indexed，更符合人类直觉。
• 合并逻辑零值：根据操作性质定义查询无交集时的返回值（求和用0，最小值用极大值，乘积用1等）。
• 懒惰标记的顺序：如果同时有复合更新（如先加后乘），需要使用多个标记并明确优先级，可参考“线段树维护乘法和加法”的进阶教程。

10. 结语

线段树通过分治和懒惰标记，将动态区间的查询与更新都控制在 O(log n)，是处理序列统计问题的基础工具。理解其递归构建与懒惰下推的精髓后，你可以轻松扩展到最大值、最小值、最大子段和等多种聚合操作。建议手写几遍核心模板，强化记忆，之后面对变种问题时便能游刃有余。