线段树（Segment Tree）的区间最值查询与更新操作详解

一、问题描述
线段树是一种二叉树结构，用于高效处理数组的区间查询（如区间求和、最值等）和单点/区间更新。本节聚焦于区间最值查询（Range Maximum Query, RMQ） 问题：给定长度为 \(n\) 的数组，需支持以下操作：

1. 查询操作 query(l, r)：返回区间 \([l, r]\) 内的最大值。
2. 更新操作 update(index, value)：将位置 index 的值修改为 value。

要求：两种操作的时间复杂度均优于 \(O(n)\)，理想目标为 \(O(\log n)\)。

二、线段树的核心思想

1. 分治预处理：

   • 将数组的每个区间 \([l, r]\) 映射到线段树的一个节点，节点存储该区间的最大值。
   • 根节点对应整个数组 \([0, n-1]\)，每个非叶子节点 \([l, r]\) 的左右子节点分别对应左半区间 \([l, mid]\) 和右半区间 \([mid+1, r]\)（其中 \(mid = \lfloor (l+r)/2 \rfloor\)）。

2. 二叉树结构：

   • 树高为 \(O(\log n)\)，每个操作最多遍历树高路径。

三、线段树的构建
假设数组为 arr = [3, 1, 4, 2, 5]，构建过程如下：

1. 递归划分区间：

   • 根节点：区间 \([0, 4]\)，最大值需计算。
   • 左子节点：区间 \([0, 2]\)，右子节点：区间 \([3, 4]\)。
   • 递归直到叶子节点（区间长度为1）。

2. 节点存储值：

   • 叶子节点：区间内仅一个元素，最大值即为该元素值。
   • 非叶子节点：最大值 = max(左子树最大值, 右子树最大值)。

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

        [0,4]: max=5
       /          \
   [0,2]: max=4   [3,4]: max=5
   /     \         /     \
[0,1]:4 [2,2]:4 [3,3]:2 [4,4]:5
 /   \
[0,0]:3 [1,1]:1

四、区间最值查询操作
查询区间 \([l, r]\) 的最大值，递归规则：

1. 当前节点区间完全包含于查询区间：直接返回节点存储的最大值。
2. 当前节点区间与查询区间无重叠：返回负无穷（不影响最大值比较）。
3. 当前节点区间部分重叠：递归查询左右子树，返回 max(左子树查询结果, 右子树查询结果)。

示例：查询 [1, 3] 的最大值（基于上述树）：

• 根节点 [0,4]：部分重叠 → 查询左右子树。
  • 左子树 [0,2]：部分重叠（查询区间覆盖了其右半部分）→ 继续递归：
    • 左子节点 [0,1]：完全包含于 [1,3]？否（仅部分重叠）→ 递归其左右子树：
      • [0,0]：无重叠 → 返回 -∞。
      • [1,1]：完全包含 → 返回 1。
    • 右子节点 [2,2]：完全包含 → 返回 4。
    • 合并结果：max(1, 4) = 4。
  • 右子树 [3,4]：部分重叠 → 递归左子节点 [3,3]（完全包含，返回 2），右子节点 [4,4] 无重叠。
  • 合并结果：max(4, 2) = 4。
• 最终结果：4。

时间复杂度：每次递归最多访问左右子树之一，树高为 \(O(\log n)\)，故为 \(O(\log n)\)。

五、单点更新操作
更新 index 位置的值，递归规则：

1. 定位到叶子节点：递归向下找到对应 index 的叶子节点。
2. 更新叶子节点值。
3. 回溯更新父节点：父节点最大值 = max(左子树最大值, 右子树最大值)。

示例：将 index=1 的值改为 6：

• 从根节点 [0,4] 向下递归：
  • 左子树 [0,2] → 其左子节点 [0,1] → 右子节点 [1,1]（叶子节点）。
• 更新 [1,1] 的值为 6。
• 回溯：
  • [0,1] 最大值变为 max(3, 6) = 6。
  • [0,2] 最大值变为 max(6, 4) = 6。
  • 根节点最大值变为 max(6, 5) = 6。

时间复杂度：更新路径长度 = 树高 \(O(\log n)\)。

六、区间更新与延迟传播（Lazy Propagation）
若需更新整个区间（如区间内所有值加常数），可结合延迟传播优化：

1. 延迟标记（Lazy Tag）：节点额外存储一个标记，表示“该区间所有值需增加的量”，但尚未递归更新子树。
2. 查询/更新时传播标记：当访问子节点前，将标记下推至左右子树，并重置当前标记。

优点：避免每次更新递归到底，将区间更新复杂度也降至 \(O(\log n)\)。

七、总结

• 核心优势：将区间操作转换为 \(O(\log n)\) 的二叉树遍历。
• 适用场景：频繁区间查询、单点/区间更新的静态或动态数组。
• 变体扩展：可通过修改节点存储值（如区间和、区间乘积）适配不同问题。