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

一、问题描述
线段树是一种用于处理区间查询（如区间求和、区间最值等）的高效数据结构。它可以在O(log n)时间复杂度内完成区间查询和单点更新操作。当需要频繁查询数组中某个区间的最小值/最大值，同时支持修改某个元素的值时，线段树是理想的选择。

二、基本概念

1. 线段树是一棵完全二叉树，每个叶子节点对应数组的一个元素
2. 每个非叶子节点代表其左右子节点对应区间的合并结果（如最小值）
3. 树的高度为O(log n)，其中n是数组长度

三、线段树构建过程

步骤1：确定树的大小

• 如果数组长度为n，线段树需要4n的空间（最坏情况）
• 使用数组存储树结构，根节点索引为1

步骤2：递归构建

def build_tree(tree, arr, node, start, end):
    if start == end:
        # 叶子节点，存储单个元素值
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        # 递归构建左子树
        build_tree(tree, arr, 2*node, start, mid)
        # 递归构建右子树  
        build_tree(tree, arr, 2*node+1, mid+1, end)
        # 当前节点值为左右子树最小值
        tree[node] = min(tree[2*node], tree[2*node+1])

示例：数组[1, 3, 2, 7, 9, 11]的线段树构建

构建过程：
1. 根节点[0,5]：min(左子树[0,2], 右子树[3,5])
2. 左子树[0,2]：min([0,1], [2,2])
3. 继续递归直到叶子节点

四、区间最值查询

步骤1：查询分解

• 从根节点开始，将查询区间[L,R]与当前节点区间[current_start, current_end]比较
• 三种情况：
  1. 完全包含：当前区间 ⊆ [L,R]，直接返回节点值
  2. 无重叠：返回极大值（对最小值查询）
  3. 部分重叠：递归查询左右子树

步骤2：递归查询实现

def query_tree(tree, node, start, end, L, R):
    if R < start or L > end:
        # 区间无重叠，返回极大值
        return float('inf')
    if L <= start and end <= R:
        # 当前区间完全包含在查询区间内
        return tree[node]
    
    # 部分重叠，递归查询
    mid = (start + end) // 2
    left_min = query_tree(tree, 2*node, start, mid, L, R)
    right_min = query_tree(tree, 2*node+1, mid+1, end, L, R)
    return min(left_min, right_min)

示例查询：在数组[1,3,2,7,9,11]中查询区间[1,4]的最小值

查询过程：
1. 根节点[0,5]：部分重叠，查询左右子树
2. 左子树[0,2]：完全包含在[1,4]内，返回值min(3,2)=2
3. 右子树[3,5]：部分重叠，继续查询
4. 最终得到min(2, min(7,9)) = 2

五、单点更新操作

步骤1：定位叶子节点

• 从根节点开始，根据索引递归找到对应的叶子节点
• 更新叶子节点的值

步骤2：回溯更新父节点

• 从叶子节点向上回溯，更新所有受影响的祖先节点

def update_tree(tree, node, start, end, idx, value):
    if start == end:
        # 找到目标叶子节点
        tree[node] = value
    else:
        mid = (start + end) // 2
        if start <= idx <= mid:
            # 目标在左子树
            update_tree(tree, 2*node, start, mid, idx, value)
        else:
            # 目标在右子树
            update_tree(tree, 2*node+1, mid+1, end, idx, value)
        # 更新当前节点值
        tree[node] = min(tree[2*node], tree[2*node+1])

示例更新：将索引2的值从2改为5

更新过程：
1. 定位到叶子节点[2,2]
2. 更新该节点值为5
3. 回溯更新父节点[0,2]：min(3,5)=3
4. 继续回溯更新根节点[0,5]：min(3,7)=3

六、时间复杂度分析

• 构建时间：O(n) - 每个节点只访问一次
• 查询时间：O(log n) - 树的高度
• 更新时间：O(log n) - 需要更新一条路径上的节点

七、实际应用场景

1. 实时股票数据区间最值查询
2. 游戏中的区间属性统计
3. 地理信息系统中的区域查询
4. 数据库查询优化中的范围查询

这种实现确保了在动态数据环境下高效处理区间最值查询需求，是许多实时系统中的核心数据结构。