01先把问题说具体
既要单点修改,又要查询任意区间的和、最大值或其他可合并信息,树状数组的前缀相减并非总适用。
02一步步得到方法
区间被反复二分
根表示整个区间,孩子表示左右两半,叶子表示单元素。每个内部节点保存两个孩子摘要的合并结果。求和用加法,最小值用 min;合并需要结合律,空区间需要单位元。
本课采用迭代布局:把叶子数补到不小于 n 的二次幂 size,叶子放在 [size,2size),父节点下标是 i//2。多出的叶子存 0,保证不改变和。
查询只取完整覆盖块
把 [l,r) 平移到叶子层。若 l 是右孩子,它的左兄弟不在范围内,所以先取 l 再 l++;若 r 是右边界对应的右孩子位置,先 --r 再取该左侧尾块。随后两端同时上移。
两边向上靠拢时,所取块互不重叠,覆盖范围逐层缩小。单点赋值则修改叶子后一路重算父节点。区间更新若想快,需要懒标记表示尚未下传的统一操作,不能仅改根摘要就当完成所有子节点。
先选聚合运算,再定义单位元
线段树每个节点保存一段区间的聚合结果。聚合应满足结合律,空段需要单位元:和是0,最小值是正无穷,最大值是负无穷。不同查询不能随意复用同一个初始值。
迭代半开区间查询分别收集左右两侧块,范围逐层缩小。若聚合不满足交换律,还必须保留左右累积次序;本课的求和掩盖了这个更一般的顺序要求。
03把一个小例子完全算清楚
[1,2,3,4] 查询 [1,4),再把下标 2 改为 10。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 叶子 | 位置 4..7 存 1,2,3,4 | 父节点 2=3,3=7 |
| 查询 | 取叶子 5 的 2,再取节点 3 的 7 | 结果 9 |
| 更新 | 叶子 6=10,节点 3=14,根=17 | 只重算祖先 |
| 再次查询 | 2+14=16 | 不访问无关节点 |
窄屏可左右滑动表格,阅读完整计算与理由。
线段树保存的是可以快速合并的区间摘要,而非每种查询的完整答案。
04为什么这个方法成立
- 建树自底向上,使每个节点等于其叶子区间之和。
- 单点赋值只影响祖先区间,重算祖先恢复不变量。
- 查询挑选不重叠且恰好覆盖目标范围的节点,合并得到正确答案。
05把推导翻译成代码
Python · 可独立运行的教学实现
class SegmentTree:
def __init__(self, a):
self.n, self.size = len(a), 1
while self.size < self.n:
self.size *= 2
self.tree = [0]*(2*self.size)
self.tree[self.size:self.size+self.n] = a
for i in range(self.size-1,0,-1):
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def assign(self, index, value):
assert 0 <= index < self.n
i = self.size + index
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def query(self, left, right):
assert 0 <= left <= right <= self.n
left += self.size; right += self.size
result = 0
while left < right:
if left % 2:
result += self.tree[left]; left += 1
if right % 2:
right -= 1; result += self.tree[right]
left //= 2; right //= 2
return result逐个理解关键决定
right -= 1- 右端不包含,必须先退一格再取尾块。
self.tree[2*i] + self.tree[2*i+1]- 父摘要只由两个孩子合并,因此更新传播每层 O(1)。
06时间、空间与实现范围
建树 O(n),存储 O(n),单点赋值和区间查询 O(log n)。
区间加的懒标记版本还需记录区间长度,并正确组合旧标记与新操作;本课代码没有该扩展。
07改变条件,检查哪里会出错
任意合并运算都可交换左右顺序
字符串连接、矩阵乘法等不交换;泛化查询需分别维护左右累计值再按顺序合并。
实现点更新却宣称范围修改也 O(log n)
范围更新通常需要额外的懒标记及合成规则,不能只改一个叶子就完成。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
区间最小值的空叶填多少?
需要一点提示
不能影响 min。
查看解析与答案
填正无穷,合并改为 min。
空查询 [2,2) 返回什么?
需要一点提示
没有任何覆盖块。
查看解析与答案
求和返回 0,其他运算返回相应单位元。
给整段加 5,根的和应增加多少?
需要一点提示
每个元素都变化。
查看解析与答案
增加 5×区间长度;懒标记保存 +5,之后访问孩子时再传播,不能只让根加 5。