ST表学习笔记

什么是ST表

ST 表（Sprase Table），也叫稀疏表。

主要用于解决 RMQ（Range Minimum/Maximum Query，区间最值查询）问题。

如何预处理ST表

实际上，ST表是一种动态规划 。

我们需要用 $O(n \log n)$ 的时间预处理一张表，然后仅需 $O(1)$ 查询区间最大/最小值。

我们设 $f_{i, j}$ 为以第 $i$ 个数为起点，长度为 $2^j$ 的区间中的最大值，这里 $f$ 的定义可以为 int f[N+5][log(N)+5];

以下是代码，其中区间终点为 $i+2^j-1 \leqslant n$，状态转移方程是 $f_{i,j} = max(f[i][j-1], f[i+2^{j-1}][j-1])$。

for (int i=1; i<=n; ++i) cin >> f[i][0];

for (int j=1; j<=20; ++j) // 枚举区间长度的指数
    for (int i=1; i+(1<<j)-1 <= n; ++i) // 枚举起点
        f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);

如何查询ST表

考虑对查询区间 $[l, r]$ 做分割、拼凑。

区间长度的指数 $k = \log(r-l+1)$

for (int i=1; i<=m; ++i) {
    cin >> l >> r;
    int k = log2(r-l+1);
    cout << max(f[l][k], f[r-(i<<k)+1][k]);
}

总结

ST表的使用范围：符合结合律并且可重复贡献的信息查询。
如果涉及区间修改，就要使用线段树。

参考文献

liangbowen - ST 表学习笔记
董晓算法 - 35 ST表 RMQ问题