第 35 课 - 线段树
学习目标
- 理解线段树的基本结构和工作原理
- 掌握线段树的构建、查询和更新操作
- 学会使用懒惰传播优化区间更新操作
- 能够解决区间求和、区间最大值等经典问题
核心概念
什么是线段树？
线段树是一种二叉树数据结构，用于高效处理区间查询和更新问题。想象你有一个数组，经常需要查询某个区间的和，同时还需要更新数组中的元素。暴力方法每次查询都要遍历整个区间，时间复杂度是O(n)。而线段树可以将这些操作优化到O(log n)。
线段树的每个节点代表一个区间：
- 叶子节点：代表单个数组元素
- 内部节点：代表其子节点区间的合并结果（如区间和、区间最大值等）
graph TD
A[根节点: 0-7] --> B[左子: 0-3]
A --> C[右子: 4-7]
B --> D[左子: 0-1]
B --> E[右子: 2-3]
C --> F[左子: 4-5]
C --> G[右子: 6-7]
D --> H[0]
D --> I[1]
E --> J[2]
E --> K[3]
F --> L[4]
F --> M[5]
G --> N[6]
G --> O[7]
线段树的结构
对于一个有n个元素的数组，线段树通常需要4n的空间（实际上是2的幂次对齐）。每个节点存储以下信息：
- 区间范围：
[l, r] - 区间信息：如区间和
sum、区间最大值max等 - 懒标记：用于区间更新时的延迟操作（稍后讲解）
代码示例
完整的线段树实现（支持区间求和）
class SegmentTree:
def __init__(self, data):
"""初始化线段树"""
self.n = len(data)
# 使用4倍空间保证足够存储
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n)
self.build(1, 0, self.n - 1, data)
def build(self, node, start, end, data):
"""构建线段树"""
if start == end:
# 叶子节点：存储原始数据
self.tree[node] = data[start]
else:
mid = (start + end) // 2
# 递归构建左右子树
left_child = 2 * node
right_child = 2 * node + 1
self.build(left_child, start, mid, data)
self.build(right_child, mid + 1, end, data)
# 合并左右子树的信息
self.tree[node] = self.tree[left_child] + self.tree[right_child]
def update(self, node, start, end, idx, val):
"""单点更新：将索引idx处的值更新为val"""
if start == end:
# 找到叶子节点，直接更新
self.tree[node] = val
else:
mid = (start + end) // 2
left_child = 2 * node
right_child = 2 * node + 1
if idx <= mid:
# 更新在左子树
self.update(left_child, start, mid, idx, val)
else:
# 更新在右子树
self.update(right_child, mid + 1, end, idx, val)
# 更新当前节点的值
self.tree[node] = self.tree[left_child] + self.tree[right_child]
def query(self, node, start, end, l, r):
"""区间查询：查询区间[l, r]的和"""
# 1. 当前区间完全在查询区间外
if end < l or start > r:
return 0
# 2. 当前区间完全在查询区间内
if l <= start and end <= r:
return self.tree[node]
# 3. 当前区间与查询区间部分重叠
mid = (start + end) // 2
left_child = 2 * node
right_child = 2 * node + 1
left_sum = self.query(left_child, start, mid, l, r)
right_sum = self.query(right_child, mid + 1, end, l, r)
return left_sum + right_sum
def update_range_lazy(self, node, start, end, l, r, val):
"""区间更新（懒惰传播）：将区间[l, r]中的每个元素增加val"""
# 应用当前节点的懒标记
if self.lazy[node] != 0:
# 当前节点有未处理的更新
self.tree[node] += (end - start + 1) * self.lazy[node]
# 将懒标记传递给子节点
if start != end:
self.lazy[2 * node] += self.lazy[node]
self.lazy[2 * node + 1] += self.lazy[node]
# 清除当前节点的懒标记
self.lazy[node] = 0
# 检查是否需要更新当前节点
if end < l or start > r or start > end:
return
# 当前区间完全在更新区间内
if l <= start and end <= r:
# 更新当前节点
self.tree[node] += (end - start + 1) * val
# 设置懒标记（不是叶子节点）
if start != end:
self.lazy[2 * node] += val
self.lazy[2 * node + 1] += val
return
# 递归更新子树
mid = (start + end) // 2
self.update_range_lazy(2 * node, start, mid, l, r, val)
self.update_range_lazy(2 * node + 1, mid + 1, end, l, r, val)
# 更新当前节点的值
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query_range_lazy(self, node, start, end, l, r):
"""区间查询（带懒惰传播）：查询区间[l, r]的和"""
# 应用当前节点的懒标记
if self.lazy[node] != 0:
self.tree[node] += (end - start + 1) * self.lazy[node]
if start != end:
self.lazy[2 * node] += self.lazy[node]
self.lazy[2 * node + 1] += self.lazy[node]
self.lazy[node] = 0
# 检查是否完全在区间外
if end < l or start > r:
return 0
# 检查是否完全在区间内
if l <= start and end <= r:
return self.tree[node]
# 递归查询子树
mid = (start + end) // 2
left_sum = self.query_range_lazy(2 * node, start, mid, l, r)
right_sum = self.query_range_lazy(2 * node + 1, mid + 1, end, l, r)
return left_sum + right_sum
# 测试示例
if __name__ == "__main__":
# 测试数组
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(f"原始数组: {arr}")
# 创建线段树
seg_tree = SegmentTree(arr)
# 查询区间[2, 5]的和（索引从0开始）
result = seg_tree.query(1, 0, len(arr)-1, 2, 5)
print(f"区间[2,5]的和: {result}") # 预期: 5+7+9+11 = 32
# 单点更新：将索引3的值从7改为10
seg_tree.update(1, 0, len(arr)-1, 3, 10)
result = seg_tree.query(1, 0, len(arr)-1, 2, 5)
print(f"更新后区间[2,5]的和: {result}") # 预期: 5+10+9+11 = 35
# 区间更新（懒惰传播）：给区间[1,4]的每个元素加2
seg_tree.update_range_lazy(1, 0, len(arr)-1, 1, 4, 2)
result = seg_tree.query_range_lazy(1, 0, len(arr)-1, 2, 5)
print(f"区间更新后[2,5]的和: {result}") # 预期: (5+2) + (10+2) + (9+2) + 11 = 41
# 测试数组变化
print("数组当前状态:")
for i in range(len(arr)):
val = seg_tree.query_range_lazy(1, 0, len(arr)-1, i, i)
print(f"索引{i}: {val}")
实践练习
练习1：基础线段树
问题描述：给定一个整数数组，实现一个线段树支持：
- 单点更新：
update(idx, val)将索引idx处的值改为val - 区间求和：
query(l, r)查询区间[l, r]的元素和
输入示例：
arr = [2, 4, 6, 8, 10]
# 更新索引2的值为5
update(2, 5)
# 查询区间[1,3]的和
query(1, 3)
预期输出：
更新后数组: [2, 4, 5, 8, 10]
区间[1,3]的和: 17 # 4 + 5 + 8 = 17
练习2：区间更新与查询
问题描述：在练习1的基础上，增加区间更新功能：
- 区间加法：
update_range(l, r, val)将区间[l, r]中的每个元素增加val - 使用懒惰传播提高效率
输入示例：
arr = [1, 2, 3, 4, 5]
# 给区间[1,3]的每个元素加3
update_range(1, 3, 3)
# 查询区间[0,4]的和
query(0, 4)
预期输出：
原始数组: [1, 2, 3, 4, 5]
区间更新后数组: [1, 5, 6, 7, 5]
区间[0,4]的和: 24 # 1+5+6+7+5 = 24
练习3：区间最大值查询
问题描述：实现一个线段树，支持：
- 单点更新：
update(idx, val) - 区间最大值查询：
query_max(l, r)查询区间[l, r]的最大值
挑战：尝试修改线段树的节点信息，使其存储区间最大值而不是区间和。
测试用例：
arr = [3, 1, 4, 1, 5, 9, 2, 6]
# 查询区间[0,7]的最大值
query_max(0, 7) # 应返回9
# 更新索引5的值为1
update(5, 1)
# 再次查询区间[0,7]的最大值
query_max(0, 7) # 应返回6
常见错误
1. 节点索引计算错误
# 错误：忘记根节点索引是1
left_child = 2 * node # 当node=0时，会得到0
# 正确：确保根节点索引为1
2. 递归终止条件错误
# 错误：没有处理区间为空的情况
if start > end: # 应该在递归开始时检查
return 0
3. 懒标记未正确处理
# 错误：在查询时忘记下推懒标记
# 正确：每次访问节点时，先检查并下推懒标记
if self.lazy[node] != 0:
self.tree[node] += (end - start + 1) * self.lazy[node]
if start != end:
self.lazy[2*node] += self.lazy[node]
self.lazy[2*node+1] += self.lazy[node]
self.lazy[node] = 0
4. 内存分配不足
# 错误：只分配了2n的空间
self.tree = [0] * (2 * n) # 可能不够用
# 正确：分配4n的空间保证足够
self.tree = [0] * (4 * n)
小结
关键要点
- 线段树结构：每个节点代表一个区间，叶子节点代表单个元素
- 时间复杂度：
- 构建：O(n)
- 查询：O(log n)
- 更新：O(log n)
- 空间复杂度：O(4n) ≈ O(n)
- 懒惰传播：优化区间更新的关键技术，通过延迟处理提高效率
- 应用范围：适合处理需要频繁区间查询和更新的问题
何时使用线段树？
- 需要频繁进行区间查询（如区间和、区间最大值等）
- 需要频繁进行单点或区间更新
- 数组大小较大，暴力方法效率过低
进阶学习建议
- 学习线段树的变体：如动态开点线段树、权值线段树
- 了解线段树与其他数据结构（如树状数组）的对比
- 尝试解决更复杂的问题：如区间覆盖、区间染色等
线段树是数据结构与算法中的重要工具，掌握它将大大提高你解决区间问题的能力。虽然实现起来相对复杂，但一旦理解其原理，就能高效处理各种区间操作问题。
练习编辑器
rust
Loading...