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

1. 线段树的基本概念

线段树是一种用于处理区间查询（如区间求和、区间最值等）与区间更新的高效数据结构。它将一个区间划分成若干个子区间，每个节点存储对应区间的信息（如和、最大值等），从而在 O(log n) 时间内完成查询和更新操作。

核心特点：

• 适用于静态或动态区间问题。
• 需要预处理构建树结构，构建时间复杂度为 O(n)。
• 支持单点更新和区间更新（结合懒惰传播优化）。

2. 线段树的存储结构

线段树通常用数组实现（类似堆的存储方式），而非显式构建二叉树。对于长度为 n 的原始数据，需要开辟 4n 大小的数组以避免越界。

节点定义（以区间和为例）：

• 每个节点存储：区间范围 [l, r]、区间和 sum、懒惰标记 lazy（用于延迟更新）。

数组存储规则：

• 根节点下标为 1（方便计算子节点）。
• 节点 i 的左子节点下标为 2*i，右子节点下标为 2*i + 1。

3. 线段树的构建（Build）

步骤：

1. 从根节点开始（区间 [0, n-1]）。
2. 递归地将区间二分，直到区间长度为 1（叶子节点）。
3. 叶子节点直接存储原始数据值，非叶子节点存储左右子节点值的和（或其他聚合信息）。

示例代码逻辑（伪代码）：

def build_tree(node, l, r):  
    if l == r:  
        tree[node] = arr[l]  # 叶子节点  
    else:  
        mid = (l + r) // 2  
        build_tree(2*node, l, mid)      # 左子树  
        build_tree(2*node+1, mid+1, r)  # 右子树  
        tree[node] = tree[2*node] + tree[2*node+1]  # 合并子区间信息  

4. 区间查询（Query）

目标：查询区间 [ql, qr] 的聚合值（如区间和）。

步骤：

1. 若当前节点区间 [l, r] 完全包含于查询区间 [ql, qr]，直接返回节点值。
2. 若当前节点区间与查询区间无重叠，返回 0（或无效值）。
3. 若部分重叠，则递归查询左右子节点，并合并结果。

示例代码逻辑：

def query_tree(node, l, r, ql, qr):  
    if ql > r or qr < l:  
        return 0  # 无重叠  
    if ql <= l and qr >= r:  
        return tree[node]  # 完全包含  
    mid = (l + r) // 2  
    left_sum = query_tree(2*node, l, mid, ql, qr)  
    right_sum = query_tree(2*node+1, mid+1, r, ql, qr)  
    return left_sum + right_sum  

5. 单点更新（Update）

目标：修改原始数据中某个位置的值，并更新线段树。

步骤：

1. 递归找到对应的叶子节点，更新其值。
2. 回溯时更新所有祖先节点的聚合值。

示例代码逻辑：

def update_tree(node, l, r, idx, value):  
    if l == r:  
        tree[node] = value  # 找到叶子节点  
    else:  
        mid = (l + r) // 2  
        if idx <= mid:  
            update_tree(2*node, l, mid, idx, value)  
        else:  
            update_tree(2*node+1, mid+1, r, idx, value)  
        tree[node] = tree[2*node] + tree[2*node+1]  # 更新父节点  

6. 区间更新与懒惰传播（Lazy Propagation）

问题：直接更新区间内每个点会导致 O(n) 时间。
解决方案：懒惰传播——延迟更新操作，仅在必要时执行。

核心思想：

• 当更新区间完全覆盖当前节点区间时，仅更新当前节点并标记懒惰值，暂不更新子节点。
• 当后续查询或更新需要进入子节点时，再将懒惰值下推（Push Down）。

懒惰传播实现步骤：

1. 更新操作：
   • 若当前节点区间完全包含于更新区间，更新当前节点值，并标记懒惰值。
   • 若部分重叠，先下推懒惰值到子节点，再递归更新左右子树。
2. 查询操作：
   • 在递归前先下推当前节点的懒惰值，确保数据正确。

示例代码逻辑：

def update_range(node, l, r, ql, qr, value):  
    if ql > r or qr < l:  
        return  
    if ql <= l and qr >= r:  
        tree[node] += (r - l + 1) * value  # 更新区间和  
        lazy[node] += value  # 标记懒惰值  
        return  
    # 下推懒惰值  
    mid = (l + r) // 2  
    push_down(node, l, r)  
    update_range(2*node, l, mid, ql, qr, value)  
    update_range(2*node+1, mid+1, r, ql, qr, value)  
    tree[node] = tree[2*node] + tree[2*node+1]  

def push_down(node, l, r):  
    if lazy[node] != 0:  
        mid = (l + r) // 2  
        # 更新左子节点  
        tree[2*node] += lazy[node] * (mid - l + 1)  
        lazy[2*node] += lazy[node]  
        # 更新右子节点  
        tree[2*node+1] += lazy[node] * (r - mid)  
        lazy[2*node+1] += lazy[node]  
        lazy[node] = 0  # 清除标记  

7. 时间复杂度分析

• 构建：O(n)
• 查询/更新：
  • 单点操作：O(log n)
  • 区间操作（懒惰传播）：O(log n)

8. 应用场景

• 动态区间求和、最值查询。
• 区间赋值、加减操作。
• 二维线段树用于平面区域查询（如矩阵操作）。

通过以上步骤，线段树可以高效处理动态区间问题，结合懒惰传播后，区间更新操作也能达到对数时间复杂度。