ST表
定义
ST 表(Sparse Table,稀疏表)是用于解决 可重复贡献问题 的数据结构。

什么是可重复贡献问题?
可重复贡献问题 是指对于运算 ,满足 ,则对应的区间询问就是一个可重复贡献问题。例如,最大值有 ,gcd 有 ,所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外, 还必须满足结合律才能使用 ST 表求解。
什么是 RMQ?
RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。解决 RMQ 问题有很多种方法,可以参考 RMQ 专题。
引入
ST 表模板题
题目大意:给定 个数,有 个询问,对于每个询问,你需要回答区间 中的最大值。
考虑暴力做法。每次都对区间 扫描一遍,求出最大值。
显然,这个算法会超时。
ST 表
ST 表基于倍增思想,可以做到 预处理, 回答每个询问。但是不支持修改操作。
基于倍增思想,我们考虑如何求出区间最大值。可以发现,如果按照一般的倍增流程,每次跳 步的话,询问时的复杂度仍旧是 ,并没有比线段树更优,反而预处理一步还比线段树慢。
我们发现 ,也就是说,区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分,只要这些区间的并是所求的区间,最终计算出的答案就是正确的。
如果手动模拟一下,可以发现我们能使用至多两个预处理过的区间来覆盖询问区间,也就是说询问时的时间复杂度可以被降至 ,在处理有大量询问的题目时十分有效。
具体实现如下:
令 表示区间 的最大值。
显然 。
根据定义式,第二维就相当于倍增的时候「跳了 步」,依据倍增的思路,写出状态转移方程:。

以上就是预处理部分。而对于查询,可以简单实现如下:
对于每个询问 ,我们把它分成两部分: 与 ,其中 。两部分的结果的最大值就是回答。

根据上面对于「可重复贡献问题」的论证,由于最大值是「可重复贡献问题」,重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 ,可以保证答案的正确性。
示例代码
注意点
-
输入输出数据一般很多,建议开启输入输出优化。
-
每次用库自带的log函数重新计算 log 函数值并不值得,建议进行如下的预处理:
ST 表维护其他信息
除 RMQ 以外,还有其它的「可重复贡献问题」。例如「区间按位与」、「区间按位或」、「区间 GCD」,ST 表都能高效地解决。
需要注意的是,对于「区间 GCD」,ST 表的查询复杂度并没有比线段树更优(令值域为 ,ST 表的查询复杂度为 ,而线段树为 ,且值域一般是大于 的),但是 ST 表的预处理复杂度也没有比线段树更劣,而编程复杂度方面 ST 表比线段树简单很多。
如果分析一下,「可重复贡献问题」一般都带有某种类似 RMQ 的成分。例如「区间按位与」就是每一位取最小值,而「区间 GCD」则是每一个质因数的指数取最小值。
总结
ST 表能较好的维护「可重复贡献」的区间信息(同时也应满足结合律),时间复杂度较低,代码量相对其他算法很小。但是,ST 表能维护的信息非常有限,不能较好地扩展,并且不支持修改操作。