稀疏表（Sparse Table）
一句话说明
稀疏表提前预处理所有长度为
2^k的区间答案，所以它适合“静态数组 + 大量区间最值查询”。
先判断它能不能用
稀疏表不是通用区间结构，它只在下面这种场景很强：
- 数组建好之后不再修改
- 查询很多
- 维护的信息满足幂等性，比如
min、max、gcd
典型反例：
核心直觉
如果我们已经知道所有长度为 1、2、4、8 … 的区间答案，
那任意区间最值就能很快拼出来。
定义：
st[k][i] = 从 i 开始，长度为 2^k 的区间答案例如当我们维护区间最小值时：
st[0][i] = nums[i]
st[1][i] = min(nums[i], nums[i+1])
st[2][i] = min(nums[i..i+3])转移也很直接：
st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)])也就是：
- 长度
2^k的区间 - 拆成两个长度
2^(k-1)的半区间
为什么查询能做到 O(1)
查询 [left, right] 时，设区间长度为 length，取：
k = floor(log2(length))然后用两个长度都是 2^k 的区间去覆盖它：
[left, left+2^k-1]
[right-2^k+1, right]这两个区间允许重叠。
之所以还能用，是因为对 min/max/gcd 这类运算来说，重复算一次没关系。
这就是稀疏表查询快的根本原因。
Go 代码：区间最小值模板
type SparseTable struct {
log []int
st [][]int
}
func NewSparseTable(nums []int) *SparseTable {
n := len(nums)
if n == 0 {
return &SparseTable{}
}
log := make([]int, n+1)
for i := 2; i <= n; i++ {
log[i] = log[i/2] + 1
}
levels := log[n] + 1
st := make([][]int, levels)
st[0] = append([]int(nil), nums...)
for k := 1; k < levels; k++ {
size := n - (1 << k) + 1
st[k] = make([]int, size)
half := 1 << (k - 1)
for i := 0; i < size; i++ {
st[k][i] = min(st[k-1][i], st[k-1][i+half])
}
}
return &SparseTable{
log: log,
st: st,
}
}
func (sp *SparseTable) QueryMin(left, right int) int {
length := right - left + 1
k := sp.log[length]
return min(sp.st[k][left], sp.st[k][right-(1<<k)+1])
}
func min(a, b int) int {
if a < b {
return a
}
return b
}这个模板里真正关键的不是代码，而是状态含义
写 ST 表最容易晕的地方是把下标含义搞混。
你只要一直咬死这个定义：
st[k][i] = 从 i 开始，长度为 2^k 的区间答案后面的建表和查询都会很自然。
如果题目求最大值怎么办
只改合并函数即可。
func max(a, b int) int {
if a > b {
return a
}
return b
}然后把建表和查询里的 min 换成 max。
稀疏表和线段树怎么选
选稀疏表
- 没有更新
- 查询非常多
- 只做最值 /
gcd/ 幂等查询 - 想把单次查询压到
O(1)
选线段树
- 题目有修改
- 查询信息更复杂
- 需要在线处理
也就是说，稀疏表是“静态查询极致优化版”，不是万能结构。
复杂度
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 预处理 | O(n log n) | O(n log n) |
| 单次查询 | O(1) | O(1) |
易错点
ST 表最常见的错误
length一定是right-left+1。- 第二段区间起点是
right-(1<<k)+1，这里特别容易少写+1。st[k]的有效长度不是n，而是n-(1<<k)+1。- 求和不是幂等操作，不能直接套这个
O(1)查询模板。
经典题目
- RMQ（Range Minimum Query）模板题
- 静态区间最大值查询
- 静态区间
gcd查询 - 倍增和 LCA 相关题目的预处理理解