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

一、问题描述
线段树是一种二叉树结构，用于高效处理区间查询（如区间和、区间最大值等）和单点/区间更新。本节重点讲解区间最大值查询（Range Maximum Query, RMQ）场景，要求支持：

• 查询操作：给定区间[L,R]，快速找出该区间内的最大值
• 更新操作：修改某个位置的值，并维护线段树结构

二、数据结构设计

1. 树节点结构：

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start  # 节点负责的区间起始下标
        self.end = end      # 节点负责的区间结束下标
        self.max_val = 0    # 存储区间最大值
        self.left = None    # 左子节点
        self.right = None   # 右子节点

2. 树构建原则：

• 叶子节点：负责单个元素（start=end），max_val=元素值
• 内部节点：负责区间[start,end]，max_val=max(左子树最大值, 右子树最大值)
• 树高度：O(log n)，n为原始数组长度

三、建树过程详解
以数组[2,5,1,4,3]为例：

1. 根节点负责[0,4]，计算mid=(0+4)//2=2
2. 递归构建左子树[0,2]：
   • 节点[0,2]的mid=1，左子树[0,1]，右子树[2,2]
   • 叶子节点[0,0]（值2）、[1,1]（值5）、[2,2]（值1）
   • 节点[0,1]的max_val=max(2,5)=5
   • 节点[0,2]的max_val=max(5,1)=5
3. 递归构建右子树[3,4]：
   • 叶子节点[3,3]（值4）、[4,4]（值3）
   • 节点[3,4]的max_val=max(4,3)=4
4. 根节点[0,4]的max_val=max(5,4)=5

四、区间最大值查询算法
查询区间[L,R]的最大值：

1. 从根节点开始遍历
2. 若当前节点区间完全包含在[L,R]内，直接返回节点max_val
3. 否则：
   • 计算mid=(start+end)//2
   • 若查询区间与左子树有重叠（L≤mid），递归查询左子树
   • 若查询区间与右子树有重叠（R>mid)，递归查询右子树
4. 合并结果：返回左右子树查询结果的最大值

示例：查询[1,3]的最大值

• 根节点[0,4]：mid=2，查询区间跨越左右子树
• 左子树[0,2]：查询[1,2]，mid=1，左子树[0,1]完全包含[1,2]? 否
  • 左子树[0,1]：查询[1,1]，返回5
  • 右子树[2,2]：返回1
  • 合并结果：max(5,1)=5
• 右子树[3,4]：查询[3,3]，返回4
• 最终结果：max(5,4)=5

五、单点更新操作
更新位置index的值为new_val：

1. 从根节点向下递归查找叶子节点[index,index]
2. 更新叶子节点的max_val=new_val
3. 回溯更新路径上所有祖先节点：
   • 内部节点的max_val=max(左子树max_val, 右子树max_val)

示例：将位置2的值从1改为6

• 更新叶子节点[2,2]的max_val=6
• 回溯更新：
  • 节点[0,2]：max_val=max(5,6)=6
  • 根节点[0,4]：max_val=max(6,4)=6

六、时间复杂度分析

• 建树：每个节点处理一次，O(n)
• 查询：每层最多访问2个节点，O(log n)
• 更新：更新路径长度与树高相关，O(log n)

七、优化技巧

1. 数组存储法：用数组模拟二叉树，避免指针开销
2. 延迟传播：区间更新时使用标记延迟更新（后续专题讲解）
3. 动态开点：处理稀疏区间时按需创建节点

八、代码实现示例

def build_tree(arr, start, end):
    if start == end:
        return SegmentTreeNode(start, end, arr[start])
    mid = (start + end) // 2
    left = build_tree(arr, start, mid)
    right = build_tree(arr, mid+1, end)
    return SegmentTreeNode(start, end, max(left.max_val, right.max_val), left, right)

def query_max(node, L, R):
    if L <= node.start and node.end <= R:  # 完全包含
        return node.max_val
    mid = (node.start + node.end) // 2
    max_val = -float('inf')
    if L <= mid:  # 与左子树有重叠
        max_val = max(max_val, query_max(node.left, L, R))
    if R > mid:   # 与右子树有重叠
        max_val = max(max_val, query_max(node.right, L, R))
    return max_val

def update(node, index, new_val):
    if node.start == node.end == index:
        node.max_val = new_val
        return
    mid = (node.start + node.end) // 2
    if index <= mid:
        update(node.left, index, new_val)
    else:
        update(node.right, index, new_val)
    node.max_val = max(node.left.max_val, node.right.max_val)

通过这种设计，线段树在O(log n)时间内同时支持区间最大值查询和单点更新，比暴力查询的O(n)有显著提升。