稀疏表 | Codeboy's Blog

形式陈述

给定静态数组 $a_0,\ldots,a_{n-1}$ 与半群运算 $\circ$ ，Sparse Table 预计算

st[k][i] = a_i\circ a_{i+1}\circ\cdots\circ a_{i+2^k-1}.

递推式为

st[k][i] = st[k-1][i]\circ st[k-1][i+2^{k-1}],

始终保持左块在前、右块在后，因此不要求交换律。预处理和空间均为 $O(n\log n)$ 。

任意非空查询区间可按二进制拆成 $O(\log n)$ 个互不重叠块，按原顺序组合，故一般结合运算的查询为 $O(\log n)$ 。若运算进一步构成幂等半群，令 $k=\lfloor\log_2(r-l+1)\rfloor$ ，则可用两个长度 $2^k$ 的重叠块：

\operatorname{ans}(l,r) = st[k][l]\circ st[k][r-2^k+1].

把左块写成 $U\circ V$ 、右块写成 $V\circ W$ ，结合律与 $V\circ V=V$ 给出 $U\circ V\circ W$ 。因此常数查询的最小常用条件是结合加幂等；交换律并非必需。

直觉

Sparse Table 为每个起点和二次幂尺度保存静态区间摘要。一般查询用二进制分解选取不重叠块；幂等运算允许故意让两个最大块重叠，因为重复的整个交叠摘要不会改变结果。

常见的 min、max、gcd 都是半格运算，所以教材常把常数查询描述为“半格情形”。半格是充分条件，却比算法真正需要的幂等半群更强。

例子与边界

稀疏表把静态区间预计算为 $2^k$ 长度块，幂等运算可用两个重叠块常数回答；线段树把区间分成不重叠节点并支持更新。前者的常数查询依赖静态性和运算性质，不能靠重建少量表项获得同样的动态接口。

区间最小值查询中，

\min(st[k][l],st[k][r-2^k+1])

即使两个块重叠也不会重复计错。区间和不幂等，重叠部分会被加两次，只能使用不重叠分解、前缀和或其他结构。

非交换幂等半群同样可以使用双块公式，只要两块内部和最终合并都保持数组顺序。左零 band $x\circ y=x$ 是形式上的例子；实践中更常见的是交换操作。若实现把两块次序交换，非交换实例会立即暴露错误。

数组更新会使覆盖该位置的许多预计算块失效，Sparse Table 因而适合静态查询。所谓 “Disjoint Sparse Table” 采用另一种预处理，可对一般结合运算提供 $O(1)$ 查询；它不是本页标准重叠结构的自动推论，应单独声明构造与空间。

推论与应用

RMQ是最典型接口：标准 Sparse Table 用 $O(n\log n)$ 预处理、空间换 $O(1)$ 查询。线性空间常数时间 RMQ则通过 Cartesian tree、 $\pm1$ 结构和微块分类降低空间，不能与 Sparse Table 等同。

二次幂分解解释表层尺度，但表项递推的正确性来自半群结合律，重叠查询的正确性来自幂等性。算法复杂度、代数契约与静态更新假设是三项独立条件，缺一项都不能从另外两项推出。

参考资料

Johannes Fischer and Volker Heun, “Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays,” SIAM Journal on Computing 40(2), 2011.
Michael A. Bender and Martín Farach-Colton, “The LCA Problem Revisited,” LATIN 2000.
OI-Wiki contributors, “Sparse Table,” 2026.