线段树的区间查询与更新

知识点描述

线段树是一种用于处理区间查询与更新操作的高效数据结构。它能以对数时间复杂度支持在数组的任意区间上进行求和、最小值、最大值等查询，同时也能支持对任意区间的元素进行批量更新（例如区间增加某个值）。线段树的核心思想是将整个区间递归地划分为若干个子区间，并为每个子区间预先计算出需要查询的聚合值，以空间换时间。

核心思想

假设有一个长度为 n 的数组 arr，线段树将其表示为一棵二叉树：

• 根节点表示整个区间 [0, n-1]。
• 每个节点表示一个区间 [l, r]，其左右子节点分别表示 [l, mid] 和 [mid+1, r]（mid = (l+r)/2）。
• 叶子节点表示单个元素区间（l == r）。
• 每个节点存储其对应区间的某种聚合值（例如区间和、最小值等）。

例如，对于数组 [1, 3, 5, 7, 9, 11]，其表示区间和的线段树结构如下（叶子节点存储元素值，非叶子节点存储子区间和）：

           [0,5]:36
         /         \
    [0,2]:9       [3,5]:27
     /    \        /    \
[0,1]:4 [2,2]:5 [3,4]:16 [5,5]:11
  /  \            /  \
[0,0] [1,1]   [3,3] [4,4]
  1      3       7      9

构建过程

线段树的构建通常采用递归方法：

1. 从根节点（区间 [0, n-1]）开始。
2. 如果当前节点是叶子节点（l == r），则存储 arr[l] 作为节点聚合值。
3. 否则，递归构建左右子节点，然后根据左右子节点的值计算出当前节点的聚合值（例如，区间和 = 左子节点和 + 右子节点和）。

构建的时间复杂度为 O(n)，因为每个节点恰好被处理一次。

区间查询

查询区间 [ql, qr] 的聚合值（以区间和为例）：

1. 从根节点开始，比较当前节点区间 [l, r] 与查询区间 [ql, qr]：
   • 如果 [l, r] 完全在查询区间内（ql <= l && r <= qr），直接返回当前节点存储的聚合值。
   • 如果 [l, r] 与查询区间无重叠（r < ql || l > qr），返回不影响结果的单位值（对于求和，返回0）。
   • 否则，递归查询左右子节点，并将两个结果合并（求和即为相加）。
2. 每次递归，要么直接返回，要么向下分裂，而每次分裂最多深入两个分支，因此查询的时间复杂度为 O(log n)。

示例：查询区间 [1, 4] 的和：

• 从根节点 [0,5] 开始，区间不完全在 [1,4] 内，分裂查询左右子节点。
• 左子节点 [0,2] 不完全在 [1,4] 内，继续分裂。
  • 其左子节点 [0,1] 完全在 [1,4] 内吗？不，区间 [0,1] 中 0 不在查询区间，所以继续分裂。
    • 叶子节点 [0,0] 不在查询区间，返回0。
    • 叶子节点 [1,1] 在查询区间，返回 arr[1]=3。
  • 其右子节点 [2,2] 完全在 [1,4] 内，返回 arr[2]=5。
• 右子节点 [3,5] 不完全在 [1,4] 内，继续分裂。
  • 其左子节点 [3,4] 完全在 [1,4] 内，返回 arr[3]+arr[4]=7+9=16。
  • 其右子节点 [5,5] 不在查询区间，返回0。
• 汇总：3 + 5 + 16 = 24，即为区间和。

区间更新

如果需要对数组的某个区间 [ul, ur] 的所有元素都加上一个值 val，最朴素的方法是逐个更新叶子节点并向上传递，但这样时间复杂度为 O(n)。为了优化，线段树引入“延迟传播”机制（Lazy Propagation），其核心思想是：

1. 更新时，如果当前节点区间完全在更新区间内，则直接更新该节点存储的聚合值，并打上一个“懒标记”，表示其子节点尚未更新。
2. 如果后续查询或更新需要进入该节点的子节点，则先将懒标记下传给子节点，并清除当前节点的懒标记。

示例：在区间 [1, 4] 上每个元素加2。

• 从根节点 [0,5] 开始，不完全在更新区间内，进入左右子节点。
• 左子节点 [0,2] 不完全在 [1,4] 内，继续下探。
  • 其左子节点 [0,1] 不完全在更新区间内，继续分裂。
    • 叶子节点 [0,0] 不在更新区间，不处理。
    • 叶子节点 [1,1] 在更新区间，将其值加2（变为5），并向上更新父节点聚合值。
  • 其右子节点 [2,2] 在更新区间，将其值加2（变为7），并向上更新父节点聚合值。
• 右子节点 [3,5] 不完全在更新区间内，继续分裂。
  • 其左子节点 [3,4] 完全在更新区间内，因此不继续下探到叶子节点，而是直接将该节点聚合值增加 (区间长度)*2 = 2*2 = 4（从16变为20），并打上懒标记 +2。
  • 其右子节点 [5,5] 不在更新区间，不处理。
• 最终，树中聚合值被更新，懒标记被记录在节点 [3,4] 上。如果后续查询涉及该节点的子节点，懒标记会被下传。

延迟传播详解

懒标记是线段树高效处理区间更新的关键。具体操作：

• 更新操作：当递归到节点 [l, r] 时：
  1. 如果 [l, r] 完全在更新区间内，更新该节点的聚合值，并增加懒标记（表示子节点待更新），然后返回。
  2. 如果当前节点有懒标记，先将懒标记下传给左右子节点（更新子节点的聚合值和懒标记），然后清除当前节点的懒标记。
  3. 如果 [l, r] 与更新区间有部分重叠，递归更新左右子节点，然后根据子节点的新聚合值更新当前节点的聚合值。
• 查询操作：类似地，在查询过程中，如果遇到带有懒标记的节点，也需要先将懒标记下传，确保聚合值正确。

时间复杂度

• 构建：O(n)
• 区间查询：O(log n)
• 区间更新（使用延迟传播）：O(log n)

应用场景

线段树广泛用于需要频繁进行区间查询和更新的场景，例如：

• 计算任意区间内的最大值、最小值、和、乘积等。
• 动态维护区间统计信息（如在线游戏中的玩家积分区间排名）。
• 计算区间内满足某种条件的元素个数（配合懒标记实现区间赋值、区间加等）。

总结

线段树通过将区间递归划分为树状结构，并配合延迟传播机制，高效支持区间查询与更新。掌握线段树的关键在于理解其递归划分思想、聚合值的维护以及懒标记的传递逻辑。在实际编码中，通常用数组来模拟二叉树，以节省指针开销。