线段树的区间查询与更新

知识点描述
线段树（Segment Tree）是一种二叉树结构，用于高效处理数组的区间查询（如区间和、最小值）和区间更新操作。它将每个区间划分为若干子区间进行预处理，使得查询和更新的时间复杂度均为O(log n)。本知识点将详细讲解线段树的构建、区间查询和区间更新原理。

一、线段树的基本结构

1. 存储方式：线段树使用数组模拟完全二叉树，每个节点存储一个区间的统计值（如区间和）
2. 对于长度为n的原始数组，线段树需要4n大小的存储空间（保证最坏情况下不会越界）
3. 节点关系（下标从1开始计数）：
   • 根节点下标为1
   • 节点i的左子节点下标为2*i
   • 节点i的右子节点下标为2*i+1

二、线段树的构建过程
以区间和查询为例，构建步骤：

1. 递归划分区间：从根节点开始，将区间不断二分
2. 叶子节点处理：当区间长度为1时，直接存储数组元素值
3. 合并子节点：非叶子节点的值=左子节点值+右子节点值

示例代码框架：

def build_tree(tree, data, node, left, right):
    if left == right:  # 叶子节点
        tree[node] = data[left]
    else:
        mid = (left + right) // 2
        build_tree(tree, data, 2*node, left, mid)      # 递归构建左子树
        build_tree(tree, data, 2*node+1, mid+1, right) # 递归构建右子树
        tree[node] = tree[2*node] + tree[2*node+1]    # 合并子节点值

三、区间查询操作
查询区间[ql, qr]的求和：

1. 从根节点开始递归查询
2. 若当前节点区间完全包含在查询区间内，直接返回节点值
3. 若与查询区间部分重叠，则分别查询左右子树

关键步骤：

• 计算中间位置mid = (left+right)//2
• 查询左子树：当ql ≤ mid时
• 查询右子树：当qr ≥ mid+1时

示例代码：

def query_tree(tree, node, left, right, ql, qr):
    if ql <= left and right <= qr:  # 完全包含
        return tree[node]
    mid = (left + right) // 2
    res = 0
    if ql <= mid:  # 查询左子树
        res += query_tree(tree, 2*node, left, mid, ql, qr)
    if qr > mid:   # 查询右子树
        res += query_tree(tree, 2*node+1, mid+1, right, ql, qr)
    return res

四、区间更新操作
单点更新可直接递归修改，区间更新需引入懒标记（Lazy Propagation）优化：

1. 懒标记原理：延迟更新操作，只有在需要时才将标记下推
2. 更新步骤：
   a. 若当前区间完全包含在更新区间内，更新节点值并设置懒标记
   b. 否则先将懒标记下推给子节点，再递归更新左右子树

懒标记更新示例（区间加值）：

def update_tree(tree, lazy, node, left, right, ul, ur, val):
    if ul <= left and right <= ur:  # 完全包含
        tree[node] += (right-left+1) * val
        lazy[node] += val
        return
    # 下推懒标记
    mid = (left+right)//2
    if lazy[node] != 0:
        tree[2*node] += (mid-left+1)*lazy[node]
        tree[2*node+1] += (right-mid)*lazy[node]
        lazy[2*node] += lazy[node]
        lazy[2*node+1] += lazy[node]
        lazy[node] = 0
    # 递归更新子树
    if ul <= mid:
        update_tree(tree, lazy, 2*node, left, mid, ul, ur, val)
    if ur > mid:
        update_tree(tree, lazy, 2*node+1, mid+1, right, ul, ur, val)
    tree[node] = tree[2*node] + tree[2*node+1]  # 更新当前节点

五、时间复杂度分析

• 构建时间复杂度：O(n)（每个节点处理一次）
• 查询/更新时间复杂度：O(log n)（树高为log n）
• 空间复杂度：O(n)（使用4n大小的数组）

六、应用场景扩展

1. 支持区间最值查询（将求和改为求最值）
2. 多维线段树处理多维数据
3. 动态开点线段树处理稀疏区间

通过以上步骤，线段树将区间操作转化为对数级别的操作，是处理区间问题的核心数据结构。掌握懒标记技巧是高效实现区间更新的关键。