稀疏表(Sparse Table)

定义

稀疏表(Sparse Table)是一种解决静态区间查询问题的数据结构,核心思想是倍增:预先计算所有起点、长度为 2 的幂的区间的答案。

原理

设 f[i][j] 表示从位置 i 开始、长度为 2^j 的区间的最值,则有转移 f[i][j] = min(f[i][j-1], f[i+2^(j-1)][j-1])。查询区间 [l, r] 时,取 k 为不超过区间长度的最大 2 的幂指数,用两个可能重叠的区间 f[l][k] 与 f[r-2^k+1][k] 合并出答案。由于最值运算满足可重复贡献(幂等)性质,重叠不影响正确性。

应用

典型用途是静态 RMQ(区间最值查询)、区间 GCD、区间按位或/与等幂等运算;也常作为求解最近公共祖先(LCA)的欧拉序方法的内部组件。

优缺点

优点是查询 O(1)、实现简单;缺点是仅支持静态数据,不支持修改,且只适用于幂等的合并运算,空间为 O(n log n)。