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

1. 问题描述与引入
线段树（Segment Tree）是一种用于高效处理区间查询和单点/区间更新的数据结构。它能以对数时间复杂度支持以下操作：

• 查询（Query）：查询任意区间 [L, R] 上的最小值（或最大值、和等）。
• 更新（Update）：修改某个位置的值，或对某个区间进行批量更新（需要配合懒标记）。

我们将以区间最小值查询和单点更新为例，详细讲解线段树的构建、查询、更新过程。假设有一个数组 arr，需要频繁查询任意子数组的最小值，并允许修改某个元素的值。

2. 线段树的基本思想
线段树是一棵近似完全二叉树，每个结点对应数组的一个区间，存储该区间的聚合信息（如最小值）：

• 根结点：对应整个数组区间 [0, n-1]。
• 叶子结点：对应单个元素 [i, i]，存储 arr[i]。
• 内部结点：存储其两个子结点信息的聚合（如两个子区间的最小值）。

例如，数组 arr = [5, 3, 7, 1, 6]，线段树结构如下（括号内为区间范围）：

                      [0,4] min=1
                     /         \
              [0,2] min=3      [3,4] min=1
              /     \           /     \
        [0,1] min=3 [2,2] min=7 [3,3] min=1 [4,4] min=6
        /     \
 [0,0] min=5 [1,1] min=3

3. 线段树的存储与构建
线段树通常用数组存储（类似堆），假设当前结点索引为 node，则：

• 左子结点索引：node * 2 + 1（或 node * 2，若从1开始编号）。
• 右子结点索引：node * 2 + 2（或 node * 2 + 1）。
• 结点存储：tree[node] 表示该结点对应区间的最小值。

构建过程（递归）：

1. 从根结点 [0, n-1] 开始。
2. 如果当前区间长度为1（叶子），则 tree[node] = arr[L]。
3. 否则，将区间分成两半：mid = (L + R) / 2，递归构建左右子树。
4. 当前结点值：tree[node] = min(tree[left], tree[right])。

def build(node, L, R, arr, tree):
    if L == R:  # 叶子结点
        tree[node] = arr[L]
    else:
        mid = (L + R) // 2
        left_child = node * 2 + 1
        right_child = node * 2 + 2
        build(left_child, L, mid, arr, tree)
        build(right_child, mid + 1, R, arr, tree)
        tree[node] = min(tree[left_child], tree[right_child])

时间复杂度：O(n)，每个结点只访问一次。

4. 区间最小值查询
给定查询区间 [ql, qr]，从根结点开始递归：

1. 如果当前结点区间 [L, R] 完全包含在 [ql, qr] 内，直接返回 tree[node]。
2. 如果当前结点区间与 [ql, qr] 无交集，返回无穷大（INF）。
3. 否则，递归查询左右子区间，返回两者的最小值。

def query(node, L, R, ql, qr, tree):
    if ql > R or qr < L:  # 无交集
        return float('inf')
    if ql <= L and R <= qr:  # 完全包含
        return tree[node]
    mid = (L + R) // 2
    left_min = query(node*2+1, L, mid, ql, qr, tree)
    right_min = query(node*2+2, mid+1, R, ql, qr, tree)
    return min(left_min, right_min)

时间复杂度：O(log n)。因为每层最多访问两个结点（当查询区间跨越左右子区间时）。

5. 单点更新
将 arr[pos] 更新为 new_val，需要更新所有包含该位置的结点：

1. 从根结点开始，递归找到叶子结点 [pos, pos]。
2. 更新叶子结点的值。
3. 回溯时重新计算父结点的最小值。

def update(node, L, R, pos, new_val, arr, tree):
    if L == R:  # 找到叶子
        arr[pos] = new_val
        tree[node] = new_val
    else:
        mid = (L + R) // 2
        if pos <= mid:
            update(node*2+1, L, mid, pos, new_val, arr, tree)
        else:
            update(node*2+2, mid+1, R, pos, new_val, arr, tree)
        tree[node] = min(tree[node*2+1], tree[node*2+2])

时间复杂度：O(log n)，只更新从根到叶子的路径上的结点。

6. 完整示例演示
以 arr = [5, 3, 7, 1, 6] 为例：

1. 构建：得到线段树 tree = [1, 3, 1, 5, 3, 7, 1, 6]（索引从0开始）。
2. 查询区间 [1,3] 的最小值：
   • 根结点 [0,4] 不完整包含，递归左右。
   • 左子 [0,2] 不完整包含，继续递归其左右。
   • 右子 [3,4] 部分包含（仅 [3,3]），返回值1。
   • 最终得到 min(3, 7, 1) = 1。
3. 更新 arr[2] = 2：
   • 更新叶子 [2,2] 为2。
   • 回溯更新父结点 [0,2] 为 min(3, 2) = 2。
   • 根结点更新为 min(2, 1) = 1。

7. 扩展到区间更新与懒标记
如果需要对区间 [L, R] 的所有元素同时增加一个值，单点更新会退化为 O(n log n)。此时需引入懒标记（Lazy Propagation）：

• 懒标记存储在结点中，表示“该区间所有元素待增加的值，但尚未传递给子结点”。
• 查询或更新时，若需要深入子结点，先将懒标记下推。
• 这样区间更新也能在 O(log n) 完成。

8. 总结
线段树的核心是分治思想和二叉树存储，它：

• 支持动态区间查询与更新。
• 查询和更新的时间复杂度为 O(log n)。
• 适用于需要频繁区间聚合操作的场景（如最小值、最大值、区间和等）。

关键注意点：

• 线段树空间复杂度为 O(4n)（保守估计）。
• 若需区间更新，务必实现懒标记以避免性能退化。
• 可灵活适配其他聚合操作（如区间和、区间乘积等）。