ST 表¶
引入¶
什么是 ST 表？
ST 表是一种基于倍增思想、用来解决可重复贡献问题的数据结构。那么什么是可重复贡献问题呢？
假设现在有一个运算 \(\operatorname{opt}\)，若 \(x\operatorname{opt}x\) 正好等于 \(x\)，那么对应的区间询问就是一个可重复贡献问题。（例如求 \(a_l\operatorname{opt}a_{l+1}\operatorname{opt}\cdots\operatorname{opt}a_r\)）。比如区间最大值、区间最大公因数。另外，\(\operatorname{opt}\) 还需要满足结合律：\(a\operatorname{opt}b\operatorname{opt}c=a\operatorname{opt}(b\operatorname{opt}c)\)，这也是快速幂、线段树等所需要的。
接下来，好渴鹅将会以静态区间最值查询为例子（简称 RMQ，Range Maximum/Minimum Query）来讲述 ST 表的实现。
算法思想¶
基于 dp 和倍增。
我们可以将区间拆分成 \(\log_2\) 个长度为 \(2^x\) 的块，然后将两个块取最大值合并成一个块，那么这个问题就成了最优子结构问题。设 \(dp_{i,j}\) 表示为 \(i\) 到 \(i+2^j-1\) 这个区间内的最大值，那么很显然 \(dp_{i,0}=a_i\)。那么我们就以 \(j\) 为拓扑序，然后将长度为 \(2^j\) 的块划分成两个 \(2^{(j-1)}\) 的块，那么第一个块的起始位置为 \(i\)，第二个块的起始位置为 \(i+2^j\)，取最大值即可。
然后对于询问，大家可能一下就可以想到将序列长度进行二进制拆解，然后调用之前的 dp 数组，在所有小块中取出最大值。这样做是 \(\mathcal O(\log_2 n)\) 的，不够优秀。
事实上，我们取最大值的数组是可以重叠的。我们就直接找到小于序列长度的最大的 \(\log\) 值，假设为 \(x\)，然后把 \(l\) 往后 \(x\) 位和 \(r\) 往前 \(x\) 位取最大值，就行了。\(\log_2 i\) 可以通过 \(\mathcal O(n)\) 的预处理快速求出。
时间复杂度：预处理 + dp \(\mathcal O(n\log_2 n)\)，询问 \(\mathcal O(1)\)。
代码¶
代码 - ST 表
void pre() {
log[1] = 0, log[2] = 1;
for (int i = 3; i <= kMaxN; i++) {
log[i] = log[i >> 1] + 1;
}
for (int j = 1; j <= kLog; 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]);
}
}
}
int query(int l, int r) {
int s = log[r - l + 1];
return max(f[l][s], f[r - (1 << s) + 1][s]);
}
补充¶
其他求区间最值的方法还有线段树和树状数组，单词询问时间复杂度为 \(\mathcal O(\log_2 n)\)。与 ST 表不同的是，这两货支持动态修改。这两货也是非常重要的数据结构，在今后的学习过程中好渴鹅会重点讲解。