线段树的区间查询与更新（基础版）

知识点描述
线段树（Segment Tree）是一种用于处理区间查询（如区间和、区间最小值等）与区间更新的高效数据结构。它将一个区间递归地划分成若干个子区间，每个树节点存储一个区间的聚合信息。线段树支持在O(log n)时间内完成区间查询和单点更新，通过懒惰传播（Lazy Propagation）可进一步优化区间更新至O(log n)。本专题重点讲解线段树的基本构建、区间查询和单点更新操作。

核心思想

1. 区间划分：将整个区间平均分成两半，递归构建左右子树，直到区间长度为1（叶子节点）。
2. 节点存储：每个节点保存其代表区间的聚合值（如区间和）。
3. 查询与更新：通过递归遍历树，将目标区间与当前节点区间匹配，组合结果或更新值。

逐步讲解
假设处理数组为arr = [1, 3, 5, 7, 9, 11]，线段树用于存储区间和。

步骤1：线段树的构建

1. 初始化

   • 根节点表示整个区间[0, 5]（索引从0开始）。
   • 区间中点mid = (0 + 5) // 2 = 2，左子树区间[0, 2]，右子树区间[3, 5]。

2. 递归构建

   • 左子树[0, 2]：中点mid=1，进一步划分成[0,1]和[2,2]。
   • 右子树[3, 5]：中点mid=4，划分成[3,4]和[5,5]。
   • 叶子节点对应单个元素（如节点[0,0]值为arr[0]=1）。

3. 合并区间值

   • 父节点值 = 左子节点值 + 右子节点值。
   • 例如节点[0,2]的值 = 节点[0,1]的值（1+3=4） + 节点[2,2]的值（5） = 9。

构建后的线段树结构（括号内为区间和）：

        [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,1](3) [3,3](7) [4,4](9)

步骤2：区间查询（以查询[2,4]的和为例）

查询区间[L,R] = [2,4]，从根节点[0,5]开始递归：

1. 访问根节点[0,5]

   • 当前节点区间[0,5]完全覆盖查询区间吗？否（查询区间是子集）。
   • 计算中点mid=2，比较查询区间边界：
     • L=2 ≤ mid=2，需查询左子树[0,2]中与[2,2]的交集。
     • R=4 > mid=2，需查询右子树[3,5]中与[3,4]的交集。

2. 查询左子树[0,2]

   • 当前区间[0,2]与查询区间[2,4]的交集为[2,2]。
   • 由于[0,2]完全包含[2,2]，直接返回节点值5。

3. 查询右子树[3,5]

   • 当前区间[3,5]与查询区间交集为[3,4]。
   • 中点mid=4，比较边界：
     • L=3 ≤ mid=4，查询左子树[3,4]（完全包含于[3,4]），返回值7+9=16。
     • R=4 ≤ mid=4，右子树[5,5]无交集，忽略。

4. 合并结果

   • 总区间和 = 左子树结果5 + 右子树结果16 = 21。
   • 验证：arr[2]+arr[3]+arr[4] = 5+7+9 = 21。

步骤3：单点更新（以更新索引3的值为10为例）

更新arr[3]=10，从根节点递归向下：

1. 访问根节点[0,5]

   • 中点mid=2，目标索引3>2，进入右子树[3,5]。
   • 更新根节点值：新值 = 左子树值9 + 右子树新值（待更新）。

2. 访问节点[3,5]

   • 中点mid=4，目标索引3≤4，进入左子树[3,4]。
   • 更新节点值：新值 = 左子树新值（待更新） + 右子树值11。

3. 访问节点[3,4]

   • 中点mid=3，目标索引3≤3，进入左子树[3,3]。
   • 更新节点值：新值 = 左子树新值（待更新） + 右子树值9。

4. 更新叶子节点[3,3]

   • 直接修改值为10，并返回。

5. 回溯更新父节点

   • [3,4]新值 = 10 + 9 = 19。
   • [3,5]新值 = 19 + 11 = 30。
   • [0,5]新值 = 9 + 30 = 39。

更新后树结构变化：

根节点值由36变为39，路径[3,5]→[3,4]→[3,3]的值依次更新。

关键点总结

• 时间复杂度：构建O(n)，查询和更新均为O(log n)。
• 空间复杂度：使用数组存储时需开4n大小空间（避免递归边界溢出）。
• 适用场景：频繁区间查询（求和、最值等）和单点更新的场景。
• 进阶优化：区间更新可通过懒惰传播（Lazy Propagation）避免重复操作，后续专题展开。