静态区间的另一种取舍
线段树能支持更新;若数组固定,预处理则可以用两个存储值回答最小值查询。我们先推导表格及假设,再比较成本。
设 为不变量组,含 个来自全序集合的值。查询使用包含端点的索引 。每次比较和数组访问计为常数时间,并假设表格索引与预先计算的对数值可放入机器的字长模型。
定义 2.1.1
(稀疏表的表项)
对每个满足 的 ,及有效起点 ,定义
第 行恰有 个有效项。不存储超出数组的区间。
建立不变量
定理 2.1.2
(二的幂长度区间)
以 建表,对 使用
每个有效表项便等于所述区间的最小值。
证明
(对行号作归纳)
基础行存储每个长度为一的区间。有效的长度 区间,在上述起点分为两个互不相交、长度为 的区间。因整段有效,两项都存在。归纳假设表示它们存储两个最小值,取其较小者即得并集的最小值。∎
建表有 行,每行至多 项:时间和存储量为 。可用 、对 令 ,在 时间建立 的 表。
用重叠区块回答查询
定理 2.1.3
(双区块查询)
设 ,,,。则 与 都存在,并且 。
证明
(两个覆盖区块)
对查询令 、、,则 。长度为 的区间 和 都位于 内,且覆盖整段,可能有重叠。因此
同时位于两个区块的索引会被考虑两次,但 ,所以最小值不变。当 时两个区块相同,这同样有效。
证明透视
使两个区块有效的两个不等式
一切取决于两个不等式。区块落在 内,是因为 ,这也说明两个存储项都存在,且不含外部元素。区块能覆盖 ,是因为 :右区块起点 ,不晚于左区块的最后一个索引,所以没有索引被漏掉。 取小一些就会留下空隙,取大一些就会有区块伸出查询范围; 是同时满足两者的唯一选择。幂等性只用于第二个不等式所保证的非空重叠。
使用预先计算的对数表,查询只需两次读取和一次比较,在所述模型下为 。此保证用于静态数组;赋值可能使许多表项失效。重建整表是一个简单有效的处理方法,而线段树专为不必重建地处理单点赋值而设计。
常见错误
(把对数向上取整)
取 会使 ,除非 是二的幂,否则 。当 时区块长度会是 ,比查询还长,区块便包含 以外的元素,而且该表项未必存在。必须向下取整,因为每个区块都得落在查询范围之内。
常见错误
(第二个区块的起点差一)
第二个区块的起点是 ,而不是 。在下面的六个值例子中,查询 的 ;若从 开始,就重复了区块 ,返回 ,漏掉索引 的值 。
例题 2.1.4
(六个值的数组)
取 。第零行是原数组,第一行为 ,第二行为 。查询 长度为五,。左区块 的最小值是 ,右区块 的最小值是 ,所以返回 。两者重叠的 对最小值无害。
例题 2.1.5
(恰好是一个区块的查询)
再用 。查询 的 、、,两个区块都是 :公式为 ,即 与 的最小值。单点查询 的 、、,公式为 。两种情形中两个区块都重合,幂等性使存储的值原样返回。
例题 2.1.6
(逐行倍增建表并回答一个查询)
设 ,故 。第一行有七项:。第二行合并相距二的两项:、、、、,得 。第三行只有一项 。查询 的 、、;两个区块是 和 ,存储的最小值为 与 。答案是 ,与直接取 的最小值一致。
反例模式
过期的表格
为六个值的数组 建立表格后,将 由 改为 ,却不更新表格。旧查询仍返回 ,但 的新最小值为 。不变量适用于建表时的数组;赋值后必须更新或重建存储数据。
结合律和幂等性解释重叠为何安全
定义 2.1.7
(相关的代数性质)
对于值域上的二元运算 ,结合律指
幂等性指 。区间聚合按元素原有的从左到右顺序进行。
最小值运算满足结合律和幂等性。最大值、正整数的最大公约数以及通常定义域上的按位与、按位或也满足这两个性质。加法满足结合律,却不满足幂等性。
命题 2.1.8
(重叠区块是安全的)
设 满足结合律与幂等性。设被查询的序列是连续各部分 的串接,其中 非空;并以 同时表示各部分的聚合值,外侧某部分为空时省略它。若一个存储区块聚合 ,另一个聚合 ,则 。
证明
(先重新分组,再吸收重叠)
将查询序列写成三个连续部分 ,其中 是非空的重叠部分。第一个存储区间聚合 ,第二个聚合 。
结合律允许我们将两者的合并重新分组为
公式中的字母表示各部分的聚合值,第二个等号使用了重叠部分聚合值的幂等性。如果某个外侧部分为空,就省略它;重叠部分仍然非空。两个区间完全相同时,公式就是 。
证明透视
每个假设在哪一步发挥作用
证明有两个动作。第一,结合律把四个因子 重新分组,而不移动其中任何一个。第二,幂等性把 合并;只有这一步用到它,而且它作用于重叠部分的聚合值,并非作用于 或 的单个元素。去掉任一假设都会破坏不同的一步,这个区块之后的两个反例就是明证:加法在第二个动作失效,平均运算则在第一个动作失效。
不同部分之间的顺序从未改变,所以这个论证不需要交换律。结合律保证区间可以这样分组,幂等性消除重复的重叠部分;两者各有作用。
两个假设可以分别去掉,而每一种去法都会给出具体的错误答案。
反例模式
用两个区间求和会将重叠部分计算两次
取数组 [3, 1, 4, 1, 5, 9, 2],查询 [1, 5]。长度为五,故使用区间 [1, 4] 和 [2, 5]。它们的和分别为 11 和 19,直接相加得到 30。
实际区间和为 20。重叠区间 [2, 4] 的和为 10,被计算了两次。加法允许改变分组,却不能消除重复数据。即使查询本身恰好是一个二的幂次长度区间,将同一区间的和加两次仍会使结果翻倍。
反过来的失败同样真实:幂等性无法弥补缺少的分组性质。
反例模式
仅有幂等性不足以保证任意聚合有效
运算 具有幂等性,却不满足结合律:,而 。
对于数组 [0, 0, 6],两个长度为二的区间的平均数分别为 0 和 3。对它们求平均得到 ,而整个区间的平均数是 2。若区间分组这一步不满足所需的代数性质,单称运算具有幂等性并不足够。
对于满足结合律但不满足幂等性的运算,普通稀疏表仍可通过不相交的分解回答查询。例如,长度为 13 的区间可从左到右分成长度为 的区间。二进制展开至多给出 个区间,因此这种查询方式需要 次合并。对不满足交换律的运算,要保持区间从左到右的顺序;如果没有单位元,就以第一个区间初始化结果。这给出了一种有效的替代方法,但不能据此声称重叠公式也有效。对于和,在可以做减法时,前缀和还是更简单的方案。
查询的两个区块何时可以重叠?
查看已存储的二次幂长度区块,覆盖一段含两端点的查询,分辨最小值为何容许重复计入元素,总和却不容许。另设的假设赋值则显示静态表中哪些摘要会改变。
原快照与查询覆盖: a=[7,2,6,3,1,5,4,8], [l,r]=[1,6].
索引和值由所选例子固定。A、B、… 标示选用的已存储区块;粗边表示覆盖的元素。表格列出每个元素被计入的次数。查询与预处理检查器互相独立。
| 原索引 | 原值 | 在查询内 | 被覆盖次数 |
|---|---|---|---|
| 0 | 7 | 否 | 0 |
| 1 | 2 | 是 | 1 |
| 2 | 6 | 是 | 1 |
| 3 | 3 | 是 | 2 |
| 4 | 1 | 是 | 2 |
| 5 | 5 | 是 | 1 |
| 6 | 4 | 是 | 1 |
| 7 | 8 | 否 | 0 |
| 区块 | 存储单元 | 含两端点的区间 | 摘要 |
|---|---|---|---|
| A | (2,1) | [1,4] | 1@4 |
| B | (2,3) | [3,6] | 1@4 |
1@4 ⊗ 1@4 = 1@4; 直接扫描摘要: 1@4.
v@i 表示最小值 v 及其最左原索引 i。同值时选较小索引。零是有效的值,也是有效的索引。
各行长度不同的预处理表
单元 (k,i) 存储 [i,i+2^k−1]。只有完全在界内的区块存在。A/B/… 标示查询读取;I 标示独立检查器。同一单元可同时标 A 及 B。选取存储单元可查看其构建,查询不变。
| k / i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 (2^0=1) | ||||||||
| 1 (2^1=2) | — | |||||||
| 2 (2^2=4) | — | — | — | |||||
| 3 (2^3=8) | — | — | — | — | — | — | — |
第 k 行有 n−2^k+1 个存储单元。虚线空位表示单元不存在,并非零摘要。假设摘要大小与合并成本皆为常数,第零层以上每个单元需要一次合并。
构建一个存储摘要
(2,1) → [1,4] → 1@4.
两个相邻而不相交的子区块
- 子区块 1: (1,1) → [1,2] → 2@1
- 子区块 2: (1,3) → [3,4] → 1@4
合并子区块摘要: 2@1 ⊗ 1@4 = 1@4.
独立假设赋值:哪些存储单元会改变?
此面板重建第二个快照作比较,绝不改变原输入、查询或所检查的单元。包含该索引的区块是可能受影响者,摘要未必实际改变。这是影响检查,并非在线更新算法。
a′[4]=0; 包含该位置的存储单元: 8; 实际改变的单元: 8. 原查询保持: [1,6] → 1@4.
| 二次幂层数 k | 包含该索引的区块起点 | 摘要实际改变的区块起点 | 改变的摘要:起点、原来 → 假设后 |
|---|---|---|---|
| 0 (2^0=1) | [4] | [4] | 4: 1@4 → 0@4 |
| 1 (2^1=2) | [3,4] | [3,4] | 3: 1@4 → 0@4; 4: 1@4 → 0@4 |
| 2 (2^2=4) | [1,2,3,4] | [1,2,3,4] | 1: 1@4 → 0@4; 2: 1@4 → 0@4; 3: 1@4 → 0@4; 4: 1@4 → 0@4 |
| 3 (2^3=8) | [0] | [0] | 0: 1@4 → 0@4 |
图中的代数规律
设 L=r−l+1、k=⌊log₂ L⌋、s=2^k。首区块 [l,l+s−1] 与末区块 [r−s+1,r] 覆盖整个查询,因为 s≤L<2s。两者重叠,L=s 时更完全相同。预先计算整数对数,便可用常数时间选 k。
把所覆盖序列写成 A、B、C,B 是重叠部分,A 或 C 可以是空的。结合律容许把两区块摘要重组为 A ⊗ (B ⊗ B) ⊗ C。幂等律消去重复的重叠摘要:B ⊗ B=B。这里不需要交换律。按字典序取 (值,索引) 的最小者,同时满足两个必要规律。
总和有结合律,却没有幂等性。[3,1,4,1,5,9,2] 的查询 [1,5] 读取总和为 11 的 [1,4],及总和为 19 的 [2,5]。结果 30 把值为 10 的重叠 [2,4] 计算两次;查询总和应为 20。即使查询长度是二次幂,重叠法也会把同一区块读取两次。
不相交分解从左至右取能放入的最大二次幂区块,再处理余下长度。这些区块分割查询,所以只需结合律。长度 13 可分成 8、4、1。从第一个区块开始折叠,非空查询便不需要单位元素。读取数为 O(log L);二次幂长度只需一次。
只有幂等性也不足够。不加权平均 x⊗y=(x+y)/2 幂等却不结合:[0,0,6] 两个重叠长二区块的平均是 0 与 3,合并得 3/2,而非整段平均 2。因此本图提供具有明确代数约定的最小值与总和,不提供会误导的平均值模式。
在上述摘要成本模型下,静态预处理的时间与空间为 O(n log n)。层数少,不代表赋值后改变的单元少:八个 1 中把索引 4 改成 0,起点为 1、2、3、4 的四个长四最小值区块全部改变。单一层可有 Θ(n) 个摘要改变。比较面板使用重建,没有提供对数时间更新。
一次总和查询相符,就能验证重叠法吗?
不能。重复元素的总和可能为零,显示结果因而巧合相符。一般方法需要相应的代数规律。总和可用不相交区块,或选择适合所需查询与更新的其他数据结构。
- 算出的查询摘要
- 1@4
- 直接扫描摘要
- 1@4
- 本次例子相符
- 是
- 方法对此运算有保证
- 是
- 区块读取次数
- 2
- 不同存储单元数
- 2
- 查询合并数
- 1
- 存储单元数
- 21
- 预处理合并数
- 13
- 查询长度 L
- 6
最小值及最左索引 · 两个重叠区块 · [1,6], L=6, k=2, s=4. 算出的查询摘要: 1@4; 直接扫描摘要: 1@4; 本次例子相符: 是. 代数条件保证此查询方法适用于这个运算。 检查存储区块: (2,1) → 1@4. 独立假设赋值:哪些存储单元会改变?: a′[4]=0; 实际改变的单元: 8.
固定整数快照,长度一至八,查询非空且包含两端点。界面预设值为 1–9,独立假设新值为 0–9;数学内核也支持 −9–9 的整数。所有显示值与计数皆精确。计数描述抽象区块和合并;参考扫描、假设重建及绘图是额外教学工作。任意更新、空区间与非常数大小摘要不在此界面范围。
使用整数对数的实现
这个类对非空输入序列保存一份快照,每行只包含有效起点。预先计算整数对数表,避免查询时使用浮点对数。值必须具有全序;例子使用整数。
class SparseMin:
def __init__(self, values):
base = list(values)
if not base:
raise ValueError("sparse table requires a nonempty array")
self.n = len(base)
self.logs = [0] * (self.n + 1)
for length in range(2, self.n + 1):
self.logs[length] = self.logs[length // 2] + 1
self.table = [base]
span = 2
while span <= self.n:
half = span // 2
previous = self.table[-1]
row = [min(previous[i], previous[i + half])
for i in range(self.n - span + 1)]
self.table.append(row)
span *= 2
def query(self, left, right):
if not 0 <= left <= right < self.n:
raise IndexError("query must be a nonempty in-bounds interval")
k = self.logs[right - left + 1]
span = 1 << k
return min(self.table[k][left],
self.table[k][right - span + 1])
查询所用的两个表项总是存在,因为所选区间均位于有效查询区间内。单元素查询使用第零行,并将同一个值合并两次。对于上面的数组,SparseMin(values).query(1, 5) 返回 1。在索引访问和值运算均为常数时间的标准模型下,预处理和存储需要 ,每次查询需要 。
行数为对数级不意味着更新也是对数时间
改变数组位置 可能影响同一行中的许多区间。区间长度为 时,满足 的每个有效起点 对应的表项都可能需要重新计算。这样的起点至多有 个。对所有层求和,可能受影响的表项少于 个,但这是线性上界,而不是对数上界。
对于显式维护的表,最坏情况确实需要线性时间。令 为二的幂,选取从零开始编号的位置 ,初始时所有值均为一,再将该位置的值改为零。在区间长度为 的一行中,起点为 的 个区间均包含修改位置,每个存储的最小值都会改变。
因此,即使只更新受影响的表项,也可能需要 的工作量。重建所有行需要 。上面的类只提供静态查询,没有更新方法。如果需要频繁更新,应选择适合这一接口的数据结构,例如课程中的线段树。
存储足够的信息以返回最左侧最小值的位置
如果查询需要返回最小值的位置,可存储数对 并按字典序比较:值较小者优先;值相等时,下标较小者优先。对这些数对取最小值仍满足结合律和幂等性,因而之前的证明均适用。
对于 [4, 1, 3, 1, 2],区间 [0, 4] 的数对最小值是 ,指向最左侧的最小值,而不是下标 3 处的相等值。向同一个类传入 [(value, index) for index, value in enumerate(values)] 即可使用这种表示。若只存储最小值,则位置信息已经丢失。
习题
快速检查
(对 ,建立最小值表的第零、一、二行。)
第 行合并第 行中相距 的两项。
解答 · 答案
各行为 、 和 。
快速检查
(用该表回答查询 ,并指出查询的两个区块。)
先算 ,再算 与 。
解答 · 答案
长度为三,故 。区块 和 的最小值为 和 ,答案是 。
快速检查
(为什么长度恰为 的区间 可以使用同一区块两次查询?)
当 时,两个区块是什么?
解答 · 答案
两个区块都等于整段,且 。
快速检查
(设 。表有多少行?最后一行有多少项?建表、存储和查询的界各是多少?)
满足 的最大 决定最后一行。
解答 · 答案
因为 ,各行为 ,共 行。最后一行有 项。建表和存储为 ;预先计算对数表并假设访问与比较为常数时间时,查询为 。
延伸阅读
Algorithms for Competitive Programming:Sparse Table 讨论二的幂长度区间表。