线段树（Segment Tree）在动态区间查询问题中的应用

题目描述

线段树是一种用于高效处理区间查询（如区间求和、区间最小值等）和单点/区间更新的数据结构。它通过将区间递归分割为子区间，并在每个节点存储子区间的聚合信息，使得查询和更新操作的时间复杂度均为 \(O(\log n)\)。典型应用场景包括动态统计数组的区间和、区间最值，或解决区间覆盖问题。

解题过程详解

步骤1：理解问题需求

假设有一个数组 arr，需要支持以下操作：

1. 查询操作：查询区间 [L, R] 的求和结果（或最小值等）。
2. 更新操作：修改某个位置 i 的值，或对区间 [L, R] 进行统一修改（如区间加一个值）。

若直接遍历区间进行查询或更新，每次操作时间复杂度为 \(O(n)\)。线段树通过预处理和树形结构将操作优化到对数时间。

步骤2：线段树的构建原理

1. 树结构设计：

   • 线段树是一棵平衡二叉树，每个叶子节点对应原数组的一个元素。
   • 非叶子节点存储其代表区间的聚合值（如子区间和）。
   • 若原数组长度为 n，线段树需要 \(4n\) 的数组空间（保守估计，保证树完全二叉树形态）。

2. 建树过程（以区间和为例）：

   • 从根节点开始，递归将区间 [L, R] 二分：
     • 中点 mid = (L + R) // 2。
     • 左子树管理 [L, mid]，右子树管理 [mid+1, R]。
   • 叶子节点直接存储原数组值；非叶子节点值为左右子节点值之和。
   • 示例：数组 [1, 3, 5, 7, 9, 11] 的线段树结构如下（节点内数字表示区间和）：

            [0-5]:36
           /        \
      [0-2]:9      [3-5]:27
       /    \      /     \
     

   [0-1]:4 [2]:5 [3-4]:16 [5]:11
   / \ /
   [0]:1 [1]:3 [3]:7 [4]:9

步骤3：区间查询操作

• 查询区间 [qL, qR] 的和：
  1. 从根节点开始，递归检查当前节点区间 [L, R] 与 [qL, qR] 的关系：
     • 若 [L, R] 完全包含于 [qL, qR]，直接返回节点值。
     • 若与左子树有重叠，递归查询左子树。
     • 若与右子树有重叠，递归查询右子树。
  2. 合并左右子树的查询结果。
• 时间复杂度：最多遍历树高 \(O(\log n)\)。

步骤4：单点更新操作

• 更新位置 i 的值：
  1. 从根节点递归向下，找到对应叶子节点 [i, i]。
  2. 更新叶子节点值，并回溯更新所有祖先节点的聚合值。
• 时间复杂度：\(O(\log n)\)。

步骤5：区间更新与延迟传播（Lazy Propagation）

• 问题：若需将区间 [uL, uR] 统一加 val，逐点更新会退化为 \(O(n\log n)\)。
• 解决方案：引入延迟标记（Lazy Tag）：
  • 更新时，若当前节点区间完全包含于 [uL, uR]，则更新当前节点值并打上标记（表示“子孙节点待更新”）。
  • 查询或更新经过该节点时，先将标记下推给子节点，再继续操作。
• 示例：区间 [0-2] 加 2：
  • 在节点 [0-2] 处更新和为 9+2*3=15，并标记 tag=2。
  • 当查询 [0-1] 时，下推标记到子节点 [0-1] 和 [2]，再返回结果。

步骤6：代码框架（以区间和为例）

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 4 * self.n  # 分配4n空间
        self.tree = [0] * self.size
        self.lazy = [0] * self.size  # 延迟标记数组
        self._build(0, 0, self.n-1, data)

    def _build(self, idx, l, r, data):
        if l == r:
            self.tree[idx] = data[l]
            return
        mid = (l + r) // 2
        self._build(2*idx+1, l, mid, data)
        self._build(2*idx+2, mid+1, r, data)
        self.tree[idx] = self.tree[2*idx+1] + self.tree[2*idx+2]

    def _push_down(self, idx, l, r):
        if self.lazy[idx] != 0:
            mid = (l + r) // 2
            # 更新左右子节点的值和标记
            self.tree[2*idx+1] += self.lazy[idx] * (mid - l + 1)
            self.lazy[2*idx+1] += self.lazy[idx]
            self.tree[2*idx+2] += self.lazy[idx] * (r - mid)
            self.lazy[2*idx+2] += self.lazy[idx]
            self.lazy[idx] = 0  # 清除当前标记

    def update_range(self, idx, l, r, uL, uR, val):
        if uL <= l and r <= uR:  # 完全覆盖
            self.tree[idx] += val * (r - l + 1)
            self.lazy[idx] += val
            return
        self._push_down(idx, l, r)
        mid = (l + r) // 2
        if uL <= mid:
            self.update_range(2*idx+1, l, mid, uL, uR, val)
        if uR > mid:
            self.update_range(2*idx+2, mid+1, r, uL, uR, val)
        self.tree[idx] = self.tree[2*idx+1] + self.tree[2*idx+2]

    def query_range(self, idx, l, r, qL, qR):
        if qL <= l and r <= qR:
            return self.tree[idx]
        self._push_down(idx, l, r)
        mid = (l + r) // 2
        res = 0
        if qL <= mid:
            res += self.query_range(2*idx+1, l, mid, qL, qR)
        if qR > mid:
            res += self.query_range(2*idx+2, mid+1, r, qL, qR)
        return res

总结

• 核心思想：通过树形结构预处理区间信息，将操作代价均摊到 \(O(\log n)\)。
• 关键优化：延迟标记支持高效区间更新。
• 适用场景：动态区间统计、区间修改问题（如排行榜更新、区间染色等）。
• 变体扩展：支持区间最值、区间乘法更新等复杂操作。