sparse table · idempotent

sparse table：预处理换 O(1) 查询

给定一个不再修改的数组 $a[0..n-1]$ ，反复回答「 $a[l..r]$ 的最小值是多少」。这个问题叫 RMQ（range minimum query）。

朴素做法每次扫一遍，单次 $O(r-l+1)$ ，查询次数一多就顶不住。前缀和与线段树那一侧给出的答案是 $O(\log n)$ 查询，代价是数据结构本身可以被修改。本页走另一个方向：既然数组不改，就允许预处理付出更多，把查询压到常数。

1 · 静态与可修改的分界

「不再修改」不是一句无关紧要的限定，它是整套方法的地基。

线段树之所以只能做到 $O(\log n)$ ，是因为它必须保留「改一个点、沿路更新到根」的能力，于是每个区间只能由 $O(\log n)$ 个不相交的节点拼出来。放弃修改能力之后，预处理可以自由地把区间之间的关系算死，查询时不必再拼，直接读现成的答案。

代价一目了然：一旦有一个元素变了，整张表作废，重建要 $O(n \log n)$ 。判据只有一条，修改与查询的比例。全静态或修改极少，本页的结构最省；两者同量级，回到线段树。

2 · 只预存 2 的幂长度的区间

全部 $\binom{n}{2}$ 个区间都存下来是 $O(n^2)$ ，空间上不可接受。sparse table 只存其中一部分：

定义 2.1（sparse table） $st[k][i]$ 是区间 $[i,\ i + 2^k)$ 上的最小值， $k$ 取 $0$ 到 $\lfloor \log_2 n \rfloor$ ， $i$ 取到 $n - 2^k$ 为止。

$k = 0$ 那一层就是原数组。往上每层由下一层拼出——长度 $2^k$ 的区间正好是两段长度 $2^{k-1}$ 的区间首尾相接：

$st[k][i] = \min\left(st[k-1][i],\ st[k-1][i + 2^{k-1}]\right)$

自底向上扫一遍就把整张表填满，每格一次比较。层数是 $\lfloor \log_2 n \rfloor + 1$ ，第 $k$ 层有 $n - 2^k + 1$ 格，总格子数

\sum_{k=0}^{\lfloor \log_2 n \rfloor} (n - 2^k + 1)

$n = 100000$ 时是 1568946 格， $n \log_2 n = 1660964$ 的 0.945 倍。这个比值随 $n$ 增大而缓慢上升：每层比「满 $n$ 格」少 $2^k - 1$ 格， $n$ 越大这部分占比越小。 $n = 1000$ 时它只有 0.902。

3 · 用两段重叠覆盖任意区间

查询 $[l, r]$ ，长度 $\text{len} = r - l + 1$ 。取 $k = \lfloor \log_2 \text{len} \rfloor$ ，则 $2^k \le \text{len} < 2^{k+1}$ 。

从左端往右取一段长 $2^k$ 的区间 $[l,\ l + 2^k)$ ，从右端往左取一段长 $2^k$ 的区间 $(r - 2^k,\ r]$ 。两段各自都在 $[l, r]$ 内（因为 $2^k \le \text{len}$ ），合起来又盖住了整个 $[l, r]$ （因为 $2 \cdot 2^k \ge \text{len} + 1 > \text{len}$ ）。查询只剩一次比较：

$\text{RMQ}(l, r) = \min\left(st[k][l],\ st[k][r - 2^k + 1]\right)$

图 3-1 · 稀疏表的分层结构与一次查询用到的两段区间。可拖动

l

与

r

观察

k

的取值、两段的位置与重叠格数，也可换数组。

$k$ 的计算不必每次调 Math.log2：预存一张 $lg[1..n]$ 递推表， $lg[i] = lg[i \gg 1] + 1$ ，查询时一次数组读取。

教科书给这张表的理由通常是「浮点在 2 的幂处会差一位， $\lfloor \log_2 8 \rfloor$ 可能算出 2」。本页在 node v26.8.1 上把 $1$ 到 $2^{22}$ 逐个比对了一遍，Math.floor(Math.log2(n)) 与真值零处不符；500 万次随机长度的查询里也一次不差。所以这张表的实际收益不是正确性而是速度：同一批 500 万次查询，查表 20.2 毫秒，Math.log2 41.1 毫秒，而 Math.clz32 写法 16.8 毫秒。最后那个比查表还快，因为它是一条位扫描指令，连数组访问都省了。

4 · idempotent 是必要条件

两段重叠了。重叠了多少格？ $2 \cdot 2^k - \text{len}$ 。而 $2^k \le \text{len} < 2^{k+1}$ 给出

2 \cdot 2^k - \text{len} \ge 2 \cdot 2^k - (2^{k+1} - 1) = 1

也就是说，两段至少重一格，一次都不例外； $\text{len}$ 恰好是 2 的幂时，两段完全重合，同一个格子被读了两次。

$\min$ 对此毫不在意，因为它 idempotent： $\min(x, x) = x$ 。 $\max$ 、 $\gcd$ 、按位与、按位或同理。把它换成求和，事情立刻崩塌：

图 4-1 · 求和版稀疏表：建表规则不变，查询法不变，格子下方是它被计入的次数。可拖动

l

与

r

观察多算出来的量，也可换成全 0 数组看唯一算得对的情形。

原本预期只有「长度不是 2 的幂」的区间会出错，写测试时才发现结论要强得多：由于重叠恒不为空，全正数组上没有一个区间能算对。全 1 的 32 元数组共 528 个区间，全部错误；长度恰为 2 的幂的那些错得最狠，答案正好是真值的两倍。唯一算得对的情形是全 0 数组，多算的那一段和恰好是 0。正确性取决于数据而不取决于结构，这样的结构不能用。

警示 · 求和需要的是不相交分解，不是重叠覆盖。真要用稀疏表求和，得把 $\text{len}$ 按二进制位拆成若干互不相交的段，查询退回 $O(\log n)$ ，那时它已经不比前缀和或线段树有优势了。disjoint sparse table 是另一条路：预处理时按中点两侧各做一遍前缀聚合，任意区间恰好跨过某一层的中点，两段天然不相交，代价是层数与实现复杂度都上去了。

5 · 三种解法的交点

预处理只有摊到足够多的查询上才划算。把三种解法的操作数统一成「读写一个数组元素」来数：

图 5-1 · 稀疏表的实际规模，以及朴素扫描、线段树、稀疏表在同一批查询下的总操作数。可改查询次数

q

观察三者的交点如何移动。

查询侧三条曲线的斜率不同：朴素是 $n$ ，线段树是 $\log n$ ，稀疏表是常数。交点只由 $q$ 决定。

原以为「 $q$ 与 $n$ 同量级」就够稀疏表翻盘，按这个口径实测下来并不是。 $n = 100000$ 、 $q = 100000$ 时线段树 3600000 次访问、稀疏表 4606838 次，线段树反而更省：预处理那 $3n\log n$ 太重，而线段树每次查询只多付 $2\lceil \log_2 n \rceil$ 次。同一口径下算出的追平点是 $q \approx 131464$ 。稀疏表真正稳赢的区间是小 $n$ 大 $q$ ，或者查询本身在热路径上、每次省下的那几十纳秒有意义的场合。

真正把这个结构变得重要的，是它能被别的问题借用。本系列随后转向树上的 LCA，欧拉序与 RMQ 归约会把 LCA 整个变成本页的 $\text{RMQ}$ ，那时本页的 $O(1)$ 查询就直接成了 LCA 的 $O(1)$ 查询。

6 · 参考文献

Bender, M. A., & Farach-Colton, M. (2000). The LCA problem revisited. In LATIN 2000: Theoretical Informatics (pp. 88–94). Springer.
Fischer, J., & Heun, V. (2006). Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In Combinatorial Pattern Matching (pp. 36–48). Springer.
cp-algorithms. Sparse Table. https://cp-algorithms.com/data_structures/sparse-table.html