存储可以合并的摘要
假设数组在两次区间查询之间会改变。对总和,我们可用逆运算把两个前缀和相减;其他摘要未必有逆。比如知道前缀最小值,也不能求出每段最小值:[1,5,7] 与 [1,2,3] 的前缀最小值数组相同,但索引 的最小值分别是 5、2。
线段树使用另一种方法:存储对齐区间的摘要,用少量互不相交区间合并回答查询。单点赋值只改变包含该点的区间摘要。核心要求是合并运算有结合律,不要求交换律或减法。
使用数组 ,,索引从零开始。全部区间左闭右开: 包含 ,且 ; 为空。单点赋值取代已有 ,不一定是在旧值上加一个量。
代数要求:结合运算与单位元
定义 1.3.1
(区间摘要的幺半群)
设摘要集合 有二元运算 ,要求结合律
并有单位元 ,满足 。区间聚合是按从左到右顺序取 乘积,空区间结果为 。这种结构称为幺半群(monoid),不一定满足 。
每个数组元素提供一个摘要,可以是值本身,也可以是足以正确合并的较丰富对象。
| 区间问题 | 摘要与合并 | 单位元 |
|---|---|---|
| 总和 | 数值,加法 | |
| 最小值 | 扩充实数,取最小 | |
| 最大值 | 扩充实数,取最大 | |
| 有序连接 | 字符串,左字符串后接右字符串 | 空字符串 |
| 固定大小矩阵乘积 | 同一固定维度方阵,矩阵乘法 | 单位矩阵 |
| 平均值 | ,分别相加总和与数目 |
平均值要等查询后才取 ,且要求 。如果只把两个平均值直接平均,当它们代表不同大小的群组时就错。结合性取决于摘要表示,不只是所求统计量的名字。
数学总和例子使用精确运算。浮点加法并非精确结合,所以结果可依赖树的括号分组。实现要规定数值含义,存储整数总和时也要使用足够范围。
补齐成完全二叉树
设 是不少于 的最小二次幂。因 ,有 。树使用数组位置 ,位置 0 不用。对 ,输入摘要放在叶 ;其余叶放单位元。
每个内部位置 的左子是 ,右子是 ,而
左子永远代表较前区间。每节点按此顺序存储其对齐叶区间的聚合。用单位元补齐不改变输入聚合。
BUILD(a[0..n-1]):
m = smallest power of two with m >= n
T[1..2m-1] = identity summaries
for i = 0 to n-1:
T[m+i] = summary of a[i]
for v = m-1 down to 1:
T[v] = T[2*v] star T[2*v+1]
单点赋值重算祖先
ASSIGN(i, newValue): // 0 <= i < n
v = m + i
T[v] = summary of newValue
v = floor(v / 2)
while v >= 1:
T[v] = T[2*v] star T[2*v+1]
v = floor(v / 2)
命题 1.3.2
(补齐树的不变量)
对补齐树的每个节点 ,令 为 之下对齐叶块从左到右的聚合,补齐的叶取单位元。则 BUILD 之后 ,每次 ASSIGN 之后也是如此。
证明
(从叶向上归纳,只有祖先会改变)
建树。 从叶向上归纳就可证明区间摘要不变量:两子代表相邻区间,父合并取得连接后的聚合。结合律保证树的分组等于所要的从左到右乘积。
赋值。 只有叶 的祖先包含被改元素,其他节点区间与它不相交,摘要仍正确。从下向上重算父,就在每个受影响层恢复不变量。因此赋值正确,不需要逆运算,也不把 newValue 当作增量。∎
时根已是叶,没有父要重算,同一程序仍有效。
为什么迭代查询需要两个累积值
从叶索引区间 、 开始,保留左、右两个累积值。左边界取出的块,接在左累积值的尾端;右边界取出的块,接在右累积值的前端。
QUERY(l, r): // 0 <= l <= r <= n
L = l + m
R = r + m
left = e
right = e
while L < R:
if L is odd:
left = left star T[L]
L = L + 1
if R is odd:
R = R - 1
right = T[R] star right
L = floor(L / 2)
R = floor(R / 2)
return left star right
根以下的层,奇数 是右子,其左兄弟不在剩余查询内,所以整个块必须现在取走。如果 就是根,直接取走就完成整个剩余块。如果 是奇数,它是被排除的右边界;最后包含的节点是 的左兄弟,索引为 ,也要先取走再上升。之后两边界都为偶数,剩余相邻对就可换成父节点。
概念视角组合
把区间看成二进块的并集
查询在每一层、每个边界至多取一个块,所以 是若干对齐块的不交并。按数组次序读,它们的大小先不减(来自左边界,在上升时取得),后不增(来自右边界)。例如 的大小是 ,即 b、cd、ef、g。两个累加器恰好各自保存这个序列的前后两半。
命题 1.3.3
(有序区间查询)
假设补齐树的不变量成立。对 ,QUERY(l, r) 返回半开区间的从左到右聚合 ;当 时为 。每层至多取两个块,所以使用 次合并。
证明
(两个累积值的覆盖与顺序)
每轮开始时,原查询聚合等于
中央块是当前层从 至 的节点,保持原顺序。起初它们恰好是所求叶,两个累积值都是单位元。
取奇数左边界,就是移除第一个中央块,接到 left 尾端。取奇数右边界,就是移除最后一个中央块,接到 right 前端,没有跳过、重复或重排任何叶。边界为偶数后,由已存储节点不变量,把两子换成父仍保留有序中央聚合;结合律允许此重新分组。
中央没有块时,left star right 就是原区间聚合。空查询不进循环,返回 。证明从未交换两个块,所以不需要交换律。
循环会终止: 轮后 而 ,所以到 时 不再成立。每轮至多取两个块,由此得到所述成本。∎
证明透视
两个累积值的证明在哪里用到各项假设
不显而易见的一步,是保留两个累积值:左块接到 left 尾端,右块接到 right 前端。循环从两端向内推进,所以在下面的追踪中,块按 的顺序出现,而不是数组顺序。把右块放在前端的理由来自不变量而不是代码:不变量准确说明了剩余中央块位于两个累积值之间。
结合律只在两个子节点换成父节点,以及最后重新分组乘积时使用。单位元用于空的累积值和补齐的叶。交换律完全没有用到。奇偶测试才是证明的实质内容:测试之后 和 都是偶数,所以中央节点构成完整的兄弟对。若省略对 的测试,节点 会被漏掉;若取 而不是 ,会加进被排除的叶。半开区间的约定使 成为不包含的边界,条件 才恰好准确。
顺序真正重要的跟踪
例题 1.3.4
(连接索引 1 至 6)
取八个单字符元素 [a,b,c,d,e,f,g,h],所以 。相关节点有 、、、。查询 。
| 轮次 | 进入时 | 取左块 | 取右块 | 之后 left | 之后 right |
|---|---|---|---|---|---|
| 1 | b | g | |||
| 2 | bcd | efg |
下一对边界为 ,结果是 bcd 后接 efg,即 bcdefg。实际遇到块的顺序是 b,g,cd,ef,不是最后数组顺序;双累积值恢复了正确顺序。
如果右更新错写成 right star T[R],第二轮会得到 gef,最后答案成为 bcdgef。总和或最小值会掩盖此错误,因为两者有交换律;有序连接则把错误显示出来。
例题 1.3.5
(补齐树上的最小值)
设 ,,使用最小值摘要,所以 。叶 为 , 为 。于是 ,,。查询 从 开始。第 1 轮: 为偶数, 为奇数,所以 ,;边界变成 。第 2 轮:两者皆偶,得 。第 3 轮: 为奇数,所以 ,;边界变成 。答案为 ,正确。补齐的叶从未被读取。
例题 1.3.6
(单个元素与空区间)
设 ,使用求和,,所以 ,。查询 的 。此时 为奇数,所以 ,; 为偶数。两者减半成 ,答案为 。查询 的 ,循环不会执行,答案是 。对 ASSIGN(0, 9), 设为 ,下一个 使循环立即结束,因为没有父节点要重算。
常见错误
(取 T[R] 而不是 T[R-1])
为奇数时,节点 本身刚好在区间之外;最后包含的节点是 ,代码会先把 减一。在八个字母的追踪中,第一个右边界是 ,而 是索引 ,在 之外。取它会把区间不包含的字符加进答案。
常见错误
(把区间当作闭区间)
查询 不含 。要连接索引 至 ,必须调用 QUERY(1, 7)。对八个字母调用 QUERY(1, 6) 会得到 bcdef,悄悄漏掉 g。若实现也接受闭区间,边界处需要转换成 。
固定大小的非交换摘要也可用仿射映射。把 表示为 ,定义合并为先施左映射,再施右映射:
复合有结合律,单位元为 。顺序重要:先 再 ,得到 ;反过来则为 。只要存储合并及所求左到右聚合采用同一定义,查询程序就适用此约定,也适用矩阵乘积约定。
使用列向量时,先施矩阵 再施 对应乘积 ,不可把这个作用约定与明确要求 的数组查询混淆。
下图追踪已解练习所用的八字母查询,并演示其中的仿射复合方法。若想独立作答,请先尝试这两题。
说清复杂度在计算什么
树有 个摘要位置,建立需 次合并,赋值重算 个祖先。查询每层至多取两个块,所以需 次合并及循环步骤。 或空区间仍有常数工作。
摘要大小固定、每次合并为常数时间时,才得到 建立时间与空间,以及 更新/查询时间。在所规定运算假设下,固定大小总和、最小值及矩阵符合此模型。真正建立长连接字符串则不同:合并要复制字符,返回 个字符至少需 。字符串跟踪证明的是有序正确性,不保证对数时间产生子字符串,也不保证全树存储的总字符数只有线性。
如果每叶是一个字符,而且 为二次幂,单是每层就存储 个字符,全树实际字符数已达 。
改变更新种类需要额外代数
反例模式
只有平均值并不是结合摘要
如果合并定义为 ,对三个输入 ,先合前两个再合第三个得到 3;先合后两个则得到 ,真正平均却是 2。这运算没有结合律,也不能正确合并不同大小群组。
应把每个输入表示为 ,分别相加两坐标,以 为单位元。查询带回总和及正确数目,非空区间可在最后正确取平均。空区间虽有明确摘要 ,平均值仍未定义。
上述算法实现单点赋值,不会因为任意改一个缓存节点,就自动实现区间更新。区间加 时,总和摘要需要实际输入数目 : 变成 。相同加法正确分配至相邻摘要的合并,而两次加法标记以相加方式复合。
更新、摘要合并及更新标记复合之间的相容性,正是懒惰传播实现必须证明的条件。如果 表示标记 对摘要的作用,统一幺半群作用设计的一组清楚充分条件是
此设计的单位标记作用为恒等映射。其他懒惰设计可把作用限于非空区间,或另外携带长度数据,并各自证明相容性。存在待处理标记时,部分覆盖的查询或更新使用子摘要之前,还要下推标记或作其他理解标记的求值;上述普通查询程序没有做这项处理。标记复合未必可交换,只有查询运算具结合律,不会自动提供这些额外更新规则。
有解练习
快速检查
(1. 从合法摘要取平均)
三个输入是 ,求每叶的总和/数目摘要、合并摘要及平均。比较两种反复未加权平均。空区间平均查询在数学上应报告什么?
解答 · 解答 1
叶为 ,合并为 ,平均为 5。两种反复平均是 及 ,两者都错。空区间摘要是 ,但平均未定义,不能报告平均零。
快速检查
(2. 解释右累积值的合并方向)
八字母跟踪第一轮后,right 是 g,下一个右块是 ef。为什么必须得到 efg 而非 gef?只测整数总和能否发现这个特定错误?
解答 · 解答 2
新取块涵盖索引 4、5,比 right 已有的索引 6 更前,必须放前端。整数加法有交换律,顺序错仍得相同总和,不能揭露此错误。即使特定运算令顺序影响看不见,正确性证明仍要求顺序。
快速检查
(3. 赋值改变查询,端点却不变)
对 [8,3,6,2,7,4,5,9] 使用最小值摘要,先求 。再把索引 3 赋值为 10,重新求该区间。之后全数组最小值是多少?
解答 · 解答 3
起初查询元素是 ,最小值 2。赋值后变成 ,最小值 4。全数组最小值仍是 3,在查询以外的索引 1。重算被改叶的祖先可恢复两个答案;每个区间都直接返回根,会得到错的查询值。
快速检查
(4. 按已规定顺序聚合仿射映射)
使用 ,按数组顺序合并 、、。求结果映射及在 2 的值。为什么树可改括号,却不能改顺序?
解答 · 解答 4
先有 ,再得 ,在 2 的值为 。复合的结合律允许两种括号分组,但不具交换律,重排映射会变成另一个查询。单位映射 使补齐及空有序乘积一致。