形式陈述

稀疏表保存

$$st[k][i]=\mathrm{op}(a_i,\dots ,a_{i+2^k-1}).$$

预处理 $O(n\log n)$。对任意结合运算，可把查询区间拆为 $O(\log n)$ 个不交二进制块；若运算还幂等，如最小值、最大值、gcd，则可用两个可能重叠的长度 $2^{\lfloor {\log }_{2}L\rfloor }$ 块在 $O(1)$ 时间回答。

直觉

把所有尺度的对齐区间预先算好；查询只需选择覆盖目标长度的少量尺度块。

例子与边界

RMQ 可用重叠两块，因为 $min(x,x)=x$。区间和不幂等，重叠会重复计数，不能使用同一 $O(1)$ 公式。结构通常不支持更新。

推论与应用

用于静态 RMQ、LCA 的 Euler 序列版本、gcd 查询和倍增思想教学。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), sparse table.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), sparse table.