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

我将详细讲解线段树在区间最小值查询和更新操作中的应用。这是线段树的基本操作之一，在许多算法问题中都有重要应用。

一、线段树的基本概念回顾

线段树是一种二叉搜索树，用于存储区间信息（如区间和、最大值、最小值等）。每个节点代表一个区间，并存储该区间的统计信息。

二、数据结构设计

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [float('inf')] * (4 * self.n)  # 存储最小值
        self.build(arr, 0, 0, self.n - 1)
    
    # 递归构建线段树
    def build(self, arr, node, start, end):
        """
        node: 当前节点在tree数组中的索引
        start: 当前节点代表的区间起点（在原数组中的索引）
        end: 当前节点代表的区间终点（在原数组中的索引）
        """
        if start == end:
            # 叶子节点，直接存储数组元素
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1  # 左子节点索引
            right_child = 2 * node + 2  # 右子节点索引
            
            # 递归构建左右子树
            self.build(arr, left_child, start, mid)
            self.build(arr, right_child, mid + 1, end)
            
            # 当前节点的值是两个子节点的最小值
            self.tree[node] = min(self.tree[left_child], self.tree[right_child])

三、区间最小值查询

步骤详解：

1. 查询目标：查找区间 [l, r] 的最小值
2. 判断当前节点区间与查询区间的关系：
   • 完全包含：如果当前节点区间完全在查询区间内，直接返回
   • 完全不相交：如果当前节点区间与查询区间没有交集，返回正无穷
   • 部分相交：继续递归查询左右子树

def query_min(self, node, start, end, l, r):
    """
    查询区间 [l, r] 的最小值
    
    node: 当前节点在tree数组中的索引
    start, end: 当前节点代表的区间
    l, r: 要查询的目标区间
    """
    # 情况1：查询区间与当前节点区间无交集
    if r < start or l > end:
        return float('inf')
    
    # 情况2：当前节点区间完全包含在查询区间内
    if l <= start and end <= r:
        return self.tree[node]
    
    # 情况3：部分重叠，需要递归查询
    mid = (start + end) // 2
    left_child = 2 * node + 1
    right_child = 2 * node + 2
    
    left_min = self.query_min(left_child, start, mid, l, r)
    right_min = self.query_min(right_child, mid + 1, end, l, r)
    
    return min(left_min, right_min)

# 对外的查询接口
def range_min_query(self, l, r):
    return self.query_min(0, 0, self.n - 1, l, r)

查询示例分析：

假设数组 arr = [1, 3, 5, 7, 9, 11]

查询区间 [1, 4] 的最小值：
1. 从根节点开始（区间[0,5]）
2. 查询左子树[0,2]，不满足完全包含
3. 查询右子树[3,5]，不满足完全包含
4. 继续递归，最终会访问：
   - 节点[1,2]（值为min(3,5)=3）
   - 节点[3,4]（值为min(7,9)=7）
5. 返回 min(3, 7) = 3

四、单点更新操作

单点更新指修改数组中某个位置的值，并更新线段树。

def update(self, node, start, end, idx, value):
    """
    将位置idx的值更新为value
    
    idx: 要更新的数组索引
    value: 新的值
    """
    # 找到叶子节点
    if start == end:
        self.tree[node] = value
    else:
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        
        # 判断要更新的位置在哪边
        if start <= idx <= mid:
            # 在左子树
            self.update(left_child, start, mid, idx, value)
        else:
            # 在右子树
            self.update(right_child, mid + 1, end, idx, value)
        
        # 更新当前节点的值
        self.tree[node] = min(self.tree[left_child], self.tree[right_child])

# 对外的更新接口
def point_update(self, idx, value):
    self.update(0, 0, self.n - 1, idx, value)

更新流程示例：

将arr[2]从5更新为2：

1. 从根节点[0,5]开始，2在左子树[0,2]
2. 进入左子树[0,2]，2在右子树[1,2]
3. 进入右子树[1,2]，找到叶子节点[2,2]
4. 更新叶子节点的值为2
5. 回溯更新父节点：
   - 节点[1,2]的值 = min(arr[1], arr[2]) = min(3, 2) = 2
   - 节点[0,2]的值 = min(arr[0], 节点[1,2]) = min(1, 2) = 1
   - 根节点[0,5]的值 = min(节点[0,2], 节点[3,5]) = min(1, 7) = 1

五、区间更新与延迟传播（Lazy Propagation）

对于区间更新（将区间[l,r]的所有值增加某个值），可以使用延迟传播优化：

def __init__(self, arr):
    self.n = len(arr)
    self.tree = [float('inf')] * (4 * self.n)
    self.lazy = [0] * (4 * self.n)  # 延迟标记数组
    self.build(arr, 0, 0, self.n - 1)

def update_range(self, node, start, end, l, r, value):
    """
    将区间[l,r]的所有元素增加value（假设为区间加操作）
    这里以增加操作为例，最小值需要相应增加
    """
    # 检查延迟标记
    if self.lazy[node] != 0:
        self.tree[node] += self.lazy[node]
        if start != end:  # 不是叶子节点，下传延迟标记
            self.lazy[2*node+1] += self.lazy[node]
            self.lazy[2*node+2] += self.lazy[node]
        self.lazy[node] = 0
    
    # 情况1：无交集
    if r < start or l > end:
        return
    
    # 情况2：完全包含
    if l <= start and end <= r:
        self.tree[node] += value
        if start != end:
            self.lazy[2*node+1] += value
            self.lazy[2*node+2] += value
        return
    
    # 情况3：部分重叠
    mid = (start + end) // 2
    self.update_range(2*node+1, start, mid, l, r, value)
    self.update_range(2*node+2, mid+1, end, l, r, value)
    self.tree[node] = min(self.tree[2*node+1], self.tree[2*node+2])

六、时间复杂度分析

七、实际应用场景

1. 滑动窗口最小值：在一系列滑动窗口中找到最小值
2. 股票价格分析：在时间序列数据中查找任意时间段内的最低价
3. 网络传输监控：监测网络延迟的最小值
4. 游戏开发：查询地图中某个区域的最低高度
5. 数据库索引：支持区间最小值查询

八、完整实现示例

class MinSegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2
            
            self.build(arr, left_child, start, mid)
            self.build(arr, right_child, mid + 1, end)
            self.tree[node] = min(self.tree[left_child], self.tree[right_child])
    
    def query(self, l, r):
        return self._query(0, 0, self.n - 1, l, r)
    
    def _query(self, node, start, end, l, r):
        # 处理延迟标记
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node]
            if start != end:
                self.lazy[2*node+1] += self.lazy[node]
                self.lazy[2*node+2] += self.lazy[node]
            self.lazy[node] = 0
        
        # 无交集
        if r < start or l > end:
            return float('inf')
        
        # 完全包含
        if l <= start and end <= r:
            return self.tree[node]
        
        # 部分重叠
        mid = (start + end) // 2
        left_min = self._query(2*node+1, start, mid, l, r)
        right_min = self._query(2*node+2, mid+1, end, l, r)
        return min(left_min, right_min)
    
    def update(self, idx, value):
        self._update(0, 0, self.n - 1, idx, value)
    
    def _update(self, node, start, end, idx, value):
        if start == end:
            self.tree[node] = value
        else:
            mid = (start + end) // 2
            if start <= idx <= mid:
                self._update(2*node+1, start, mid, idx, value)
            else:
                self._update(2*node+2, mid+1, end, idx, value)
            self.tree[node] = min(self.tree[2*node+1], self.tree[2*node+2])
    
    def update_range(self, l, r, value):
        self._update_range(0, 0, self.n - 1, l, r, value)
    
    def _update_range(self, node, start, end, l, r, value):
        # 处理延迟标记
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node]
            if start != end:
                self.lazy[2*node+1] += self.lazy[node]
                self.lazy[2*node+2] += self.lazy[node]
            self.lazy[node] = 0
        
        # 无交集
        if r < start or l > end:
            return
        
        # 完全包含
        if l <= start and end <= r:
            self.tree[node] += value
            if start != end:
                self.lazy[2*node+1] += value
                self.lazy[2*node+2] += value
            return
        
        # 部分重叠
        mid = (start + end) // 2
        self._update_range(2*node+1, start, mid, l, r, value)
        self._update_range(2*node+2, mid+1, end, l, r, value)
        self.tree[node] = min(self.tree[2*node+1], self.tree[2*node+2])

# 使用示例
arr = [1, 3, 2, 7, 9, 11]
seg_tree = MinSegmentTree(arr)

print(seg_tree.query(0, 2))  # 输出: 1 (区间[0,2]的最小值)
seg_tree.update(1, 0)  # 将arr[1]更新为0
print(seg_tree.query(0, 2))  # 输出: 0
seg_tree.update_range(2, 4, -2)  # 区间[2,4]每个元素减2
print(seg_tree.query(2, 4))  # 输出: 0 (原arr[2]=2, arr[4]=9，减2后最小为0)

九、总结

线段树的区间最小值查询和更新操作通过树形结构将区间操作的时间复杂度优化到O(log n)，关键点在于：

1. 节点设计：每个节点存储对应区间的最小值
2. 递归分割：通过递归将大区间分割为小区间
3. 区间合并：利用子区间信息计算父区间信息
4. 延迟传播：对于区间更新操作，使用延迟标记避免不必要的更新

这种数据结构在处理需要频繁区间查询和更新的场景中非常高效，是算法竞赛和实际工程中常用的工具之一。