线段树（Segment Tree）的区间查询与更新

题目描述

线段树是一种用于高效处理区间查询和区间更新的数据结构。它可以支持在数组的某个区间上进行查询（如求和、最小值、最大值等）和更新（如对某个元素或某个区间进行修改），并且这两种操作的时间复杂度通常为O(log n)。线段树的基本思想是将整个数组递归地划分成若干小区间，并为每个区间维护一个值（如区间和），从而在查询和更新时，通过组合这些小区间的值来快速计算结果。

知识点背景

• 适用场景：当问题涉及对一个静态或动态数组进行频繁的区间查询和区间更新时，线段树是常用的优化工具。例如，求区间和、区间最小值、区间最大值，或者对区间进行加法、赋值等更新操作。
• 核心思想：线段树本质上是一棵二叉树，每个节点代表数组中的一个区间。根节点代表整个数组，每个叶子节点代表单个元素，非叶子节点代表其左右子节点区间的合并（如求和、最小值等）。
• 时间复杂度：构建O(n)，查询O(log n)，更新O(log n)。空间复杂度通常为O(4n)（保守估计，因为最坏情况下需要4n个节点）。

解题过程

我将以区间和查询和单点更新为例，详细讲解线段树的构建、查询和更新过程。整个过程分为四个步骤：

步骤1：线段树的构建

目标：从原始数组构建线段树，每个节点存储对应区间的和。

过程：

1. 节点表示：每个线段树节点通常包含三个信息：区间左边界l、区间右边界r，以及该区间的和sum。在实现中，我们常用数组tree来存储节点，其中tree[i]表示节点i的区间和，而l和r可以通过计算或传递参数得到。
2. 递归划分：从根节点（区间[0, n-1]）开始，将区间一分为二：左子区间为[l, mid]，右子区间为[mid+1, r]，其中mid = (l + r) / 2。递归构建左右子树，直到区间长度为1（叶子节点）。
3. 合并值：每个非叶子节点的区间和等于其左右子节点的区间和之和。

示例：
假设原始数组为arr = [1, 3, 5, 7, 9, 11]，n=6。构建的线段树如下（节点中数字表示区间和）：

根节点: [0,5] 和=36
├── 左子节点: [0,2] 和=9
│   ├── [0,1] 和=4
│   │   ├── [0,0] 和=1
│   │   └── [1,1] 和=3
│   └── [2,2] 和=5
└── 右子节点: [3,5] 和=27
    ├── [3,4] 和=16
    │   ├── [3,3] 和=7
    │   └── [4,4] 和=9
    └── [5,5] 和=11

在数组tree中，我们通常从索引1开始存储根节点，左子节点索引为2*i，右子节点索引为2*i+1。

构建的伪代码（递归实现）：

function build(node, l, r):
    if l == r:
        tree[node] = arr[l]  // 叶子节点
    else:
        mid = (l + r) / 2
        build(2*node, l, mid)      // 构建左子树
        build(2*node+1, mid+1, r)  // 构建右子树
        tree[node] = tree[2*node] + tree[2*node+1]  // 合并区间和

初始调用：build(1, 0, n-1)。

步骤2：区间查询

目标：查询数组某个区间[ql, qr]的和。

过程：

1. 递归查询：从根节点开始，检查当前节点区间[l, r]与查询区间[ql, qr]的关系：
   • 如果[l, r]完全包含在[ql, qr]内（即ql <= l && r <= qr），则直接返回当前节点的和。
   • 如果[l, r]与[ql, qr]完全不重叠，则返回0（对求和查询而言）。
   • 否则，递归查询左右子节点，并将结果相加。
2. 时间复杂度：由于每次递归都会将区间一分为二，最多访问O(log n)个节点。

示例：
查询arr中区间[1,4]的和（即3+5+7+9=24）。查询过程如下：

• 从根节点[0,5]开始，不满足完全包含，递归查询左右子节点：
  • 左子节点[0,2]：不完全包含，递归查询其子节点：
    • 节点[0,1]：完全包含在[1,4]内？不，因为区间[0,1]与[1,4]重叠但不完全包含，继续递归：
      • 节点[0,0]：不重叠，返回0。
      • 节点[1,1]：完全包含，返回3。
    • 节点[2,2]：完全包含，返回5。
  • 右子节点[3,5]：不完全包含，递归查询其子节点：
    • 节点[3,4]：完全包含，返回16。
    • 节点[5,5]：不重叠，返回0。
• 合并结果：3 + 5 + 16 = 24。

查询的伪代码：

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

初始调用：query(1, 0, n-1, ql, qr)。

步骤3：单点更新

目标：更新数组中的某个元素，并维护线段树。

过程：

1. 递归更新：从根节点开始，根据目标位置pos递归地找到对应的叶子节点，更新其值，然后回溯更新所有祖先节点的区间和。
2. 时间复杂度：每次更新需要修改从根到叶子的路径上所有节点，路径长度为O(log n)。

示例：
将arr[2]从5更新为10（即数组变为[1,3,10,7,9,11]）。更新过程如下：

• 从根节点[0,5]开始，pos=2在左子树[0,2]中，递归进入左子节点。
• 在节点[0,2]中，pos=2在右子树[2,2]中，递归进入。
• 更新叶子节点[2,2]的和为10。
• 回溯更新祖先节点的和：
  • 节点[0,2]的和变为：左子节点[0,1]的和4 + 右子节点[2,2]的和10 = 14。
  • 根节点[0,5]的和变为：左子节点[0,2]的和14 + 右子节点[3,5]的和27 = 41。

更新的伪代码：

function update(node, l, r, pos, new_val):
    if l == r:  // 找到叶子节点
        tree[node] = new_val
    else:
        mid = (l + r) / 2
        if pos <= mid:
            update(2*node, l, mid, pos, new_val)  // 更新左子树
        else:
            update(2*node+1, mid+1, r, pos, new_val)  // 更新右子树
        tree[node] = tree[2*node] + tree[2*node+1]  // 更新当前节点和

初始调用：update(1, 0, n-1, pos, new_val)。

步骤4：区间更新与懒惰传播

目标：高效处理区间更新（如对区间内所有元素加一个值）。如果使用普通单点更新，区间更新需要O(n log n)，效率低。引入懒惰传播（Lazy Propagation） 优化，可将区间更新的时间复杂度降为O(log n)。

懒惰传播思想：

• 在更新区间时，不立即更新所有子节点，而是将更新信息“懒惰地”存储在节点中，等到后续查询或更新需要时才真正传递下去。
• 每个节点维护一个lazy值，表示该节点对应的区间需要增加的值（但尚未传递到子节点）。

过程（以区间加法更新为例）：

1. 更新操作：当更新区间[ul, ur]时，从根节点开始：
   • 如果当前节点区间完全包含在更新区间内，则更新当前节点的区间和，并累加lazy值，然后返回（不继续向下传递）。
   • 否则，先将当前节点的lazy值传递给子节点（即“传播”），然后递归更新左右子节点，最后更新当前节点的区间和。
2. 查询操作：查询时也需要先传播lazy值，确保结果正确。

示例：
在arr = [1,3,5,7,9,11]上，对区间[1,4]的每个元素加2。更新过程：

• 根节点[0,5]：不完全包含，传播lazy（当前lazy=0），递归更新左右子节点。
  • 左子节点[0,2]：不完全包含，传播lazy，递归更新：
    • 节点[0,1]：不完全包含，传播lazy，递归更新：
      • 节点[0,0]：不重叠，跳过。
      • 节点[1,1]：完全包含，更新其和：3+2=5，并设置lazy=0（因为是叶子节点）。
    • 节点[2,2]：完全包含，更新其和：5+2=7。
  • 右子节点[3,5]：不完全包含，传播lazy，递归更新：
    • 节点[3,4]：完全包含，更新其和：16+2*2=20，并设置lazy=2（表示子节点待更新）。
    • 节点[5,5]：不重叠，跳过。
• 回溯更新祖先节点的和，并合并lazy值。

懒惰传播的伪代码（简略版）：

// 传播lazy值到子节点
function propagate(node, l, r):
    if lazy[node] != 0:
        tree[node] += (r - l + 1) * lazy[node]  // 更新当前节点和
        if l != r:  // 非叶子节点
            lazy[2*node] += lazy[node]
            lazy[2*node+1] += lazy[node]
        lazy[node] = 0

// 区间更新
function update_range(node, l, r, ul, ur, val):
    propagate(node, l, r)  // 先传播已有的lazy
    if ul > r or ur < l: return
    if ul <= l and r <= ur:  // 完全包含
        lazy[node] += val
        propagate(node, l, r)  // 更新当前节点
        return
    mid = (l + r) / 2
    update_range(2*node, l, mid, ul, ur, val)
    update_range(2*node+1, mid+1, r, ul, ur, val)
    tree[node] = tree[2*node] + tree[2*node+1]

总结

• 线段树通过将区间递归划分，以O(log n)的时间支持区间查询和更新。
• 单点更新和区间查询是基础操作，而懒惰传播能高效处理区间更新。
• 实际应用中，线段树可扩展到维护区间最小值、最大值等其他信息，或支持更复杂的更新操作。

通过上述步骤，你可以理解线段树的核心原理，并能实现基本的区间查询和更新功能。对于懒惰传播，需要多练习以掌握其传递时机。