前缀最小值为何不能相减
设 为实数,。我们需要两个操作:把 换成指定值,以及对 求 。前面的 Fenwick 树一课解释了为何两个前缀最小值无法决定任意区间最小值。这个限制不妨碍其他数据结构解决此问题。
线段树存储一族嵌套区间的数据。这里使用单点赋值而非增量。线段树与 Fenwick 树是不同结构;它通过存储的不变量直接处理区间最小值及赋值。
建树与不变量
定义 1.2.1
(最小值线段树)
设 为实数,。最小值线段树是以 为根的二叉树。当 ,区间 的节点有两个子节点 和 ,其中 。叶节点 存储 ,每个内部节点存储两个子节点所存值的最小值。节点 所存储的值记作 。
对树由叶向上作归纳,所存储的值满足不变量
子区间把父区间分割,不遗漏任何元素,也不包含区间外元素。重复分割后恰有 个叶节点。每个内部节点有两个子节点,所以树共有 个节点,能在 时间和空间内自底向上建成。
要赋值 ,沿唯一包含 的子节点下降,把叶节点值换成 ,再沿路返回并重新计算最小值。路径外的叶节点不变;路径上每次由已正确的子节点重新计算,恢复不变量。因此更新后根及其他所有节点都正确。无论 比旧值大还是小,方法均适用。
查询与成本
查询 时从根递归访问。对节点区间 :
- 若 与 不相交,返回 ;
- 若 ,返回它存储的最小值;
- 否则返回两个子节点结果的最小值。
符号 是最小值运算的概念性单位元,并非数组元素:。公开查询要求非空有效区间,故最终答案有限。实现也可用明确的空结果标记表示不相交。
命题 1.2.2
(最小值线段树的正确性与成本)
设 上的最小值线段树满足不变量,并假设数值比较、索引与每个数值的存储都是常数成本。
- 按上述方式作单点赋值 后,每个节点的不变量再次成立。
- 对 ,查询返回 。
- 树高至多 ;查询每一层至多访问四个节点,赋值每一层访问一个节点。因此两种操作都耗时 ,包括 。
证明
(沿路重算、区间覆盖与四节点界)
赋值。 区间不含 的节点只依赖 以外的叶节点,所以其存储值不变而且仍然正确。区间含 的节点构成由叶节点 到根的路径。叶节点现在存储 。由下而上,路径上每个节点都重新取两个子节点的最小值:其中一个子节点在路径上,已经正确;另一个不在路径上,没有改变且正确。两个子区间分割父区间,所以两个存储值的最小值就是父区间上的最小值。因此每个节点的不变量都成立。
查询。 对被访问的节点 ,以 表示它返回的值,并约定 。对 的高度作归纳,证明 。若 与 不相交,集合为空,。若 ,由不变量得 。否则 与 相交但不被包含,所以 至少有两个元素,是内部节点。它的两个子区间 分割 ,因此 是 与 的不相交并集,两个子结果的最小值就是并集上的最小值。在根处 非空,所以答案有限。
成本。 在深度 ,每个区间至多有 个元素,所以树高至多 。称与 相交但不被包含的节点为部分相交节点。若一个区间既含 内的索引又含其外的索引,它必含两个相邻索引,其中恰有一个在 内;所以部分相交节点必同时含 和 ,或同时含 和 。同一深度的节点区间互不相交,所以每层至多一个节点含 、至多一个节点含 ,即每层至多两个部分相交节点。查询只在部分相交节点之下递归,因此每层至多访问四个节点,合共至多 个。赋值沿一条根到叶的路径进行。每次访问的成本为常数。∎
证明透视
查询归纳法对最小值运算的要求
不显而易见的一步,是对每个被访问的节点都证明同一个命题,而不只是完全覆盖的节点。约定 后,不相交、被覆盖和需要分拆三种情形共用一个命题,一次归纳就能处理。
分拆的情形只用到两件事:子区间分割 ,以及并集的最小值等于两个最小值的最小值。证明从未用到幂等性,所以同一证明适用于任何有单位元的结合运算,例如以 为单位元的求和。不相交的情形正是需要单位元的原因:它必须对每个 都满足 。
成本论证用到树的另一个性质:同一深度的区间互不相交。正是这一点,把“部分相交节点含有跨过 或 的相邻索引对”变成“每层至多两个部分相交节点”。若子区间可以重叠,每层至多访问四个节点的界就不再成立。
常见的失败有两种:对不相交节点返回错误的值,以及用比赋值更弱的更新规则。下面两个区块各给一个具体例子。
反例模式
零不是不相交节点的安全返回值
断言:不相交节点可以返回 ,因为看似中性的数不会影响答案。取 。根 有子节点 和 。查询 :根是部分相交节点,子节点 被覆盖并返回 ,子节点 不相交,按此断言返回 。根于是返回 ,而真正答案是 。对任何有限值 ,只要数组各元素都大于 ,同样失败,因为此时 。不相交的返回值必须对每个 都满足 ,这迫使 ,或使用明确的空结果标记。
常见错误
(把赋值当作减小)
很容易想到把路径上每个节点更新为 。当 不大于旧叶节点值时这是对的,但值增大时就错。在 上赋值 :此规则在叶节点及其上方都保留 ,因此查询 仍返回 ;可是数组现在是 ,答案应为 。值增大可能移走原来的最小值,所以每个祖先都必须由两个子节点重新计算。
更新例子
例题 1.2.3
(五个数的查询与赋值)
从 开始。根 分成 和 。查询 时合并 、 和 的值,得 。现在赋值 。重新计算 得 ,根得 。同一查询现在返回 。单点赋值不是把 加到旧值上。
例题 1.2.4
(一次查询访问的节点)
在 上,节点依次为 ,然后 和 ,然后 、、、,再然后 和 。查询 访问全部九个节点。根、、 和 是部分相交节点。叶节点 、、 被覆盖,分别返回 、、;叶节点 和 不相交,返回 。所以 返回 , 返回 , 返回 ,根返回 。各层访问的节点数为 ,没有超过四个。
例题 1.2.5
(只有一个叶节点的树)
设 ,。根 同时是唯一的叶节点,没有子节点,也没有祖先。查询 时根被完全覆盖,返回 。赋值 只是替换存储值;没有路径需要重算,所以下一次查询返回 。两个操作都是常数时间,与 一致。
习题与解答
快速检查
(减小值。从 出发,赋值 。 的最小值及根的最小值是多少?)
解答 · 答案
两者都是 。数组变成 ;只需重新计算叶节点 的祖先,即 和根。
快速检查
(完全覆盖查询。为何建树后查询 只需常数时间?)
解答 · 答案
根被完全覆盖且已存有所求答案,不需访问子节点。
快速检查
(单点查询。在 上,查询 访问哪些节点?返回什么?)
解答 · 答案
访问 、、、 和 。节点 和 不相交,返回 ;叶节点 被覆盖,返回 ,所以答案是 。
快速检查
(节点计数。 时,树有多少个叶节点、多少个节点?)
解答 · 答案
有 个叶节点和 个内部节点,因为每个内部节点有两个子节点,而树有 个叶节点。总数为 。