ST表学习笔记

0.定义 & 基本思想#

ST 表是用来处理可重复贡献问题的，即 $x opt x = x$，且 $opt$ 须有结合律（但是这玩意一般运算都有）

所以，ST 表可以来解决区间 MIN/MAX/GCD/LCM… 等问题。

基于倍增与 DP 思想，可以做到 $\Theta(n \log n)$ 预处理，$\Theta(1)$ 查询，所以有些时候优于线段树，但是不支持修改。

但是，ST 表不支持修改

修改请移步至线段树

1.实现#

设 $st _ {i,j}$ 为区间 $[i,i + 2 ^ j - 1]$ 的需要维护的值

依言顶针可得，$st _ {i,0} = a _ i$。

由定义式得，$st _ {i,j} = opt(st _ {i,j - 1},st _ {i + 2 ^ {j - 1},j - 1})$

至此，预处理完毕。

对于一个查询，可以分为两个部分：$[l,l + 2 ^ {len} - 1],[r - 2 ^ {len} + 1,r]$

所以，答案即为 $opt(st _ {l,len}, st _ {r - 2 ^ {len} + 1,len})$。

常数较小，并且比线段树简单的多，所以没有修改操作就可以写 ST 表。

记得预处理 $\log _ 2$ 的值，不然有可能被卡掉。

24.11.16 的考试一视同仁，两个一起卡

2.代码模板#

以区间最小值举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

constexpr int MAXN = ...,MXLG = (自己开计算器算一下);
int a[MAXN],st[MAXN][MXLG],lg[MAXN];
lg[0] = -1; //准备预处 log _ 2 的值
for(int i = 1;i <= n;i++)
{
    lg[i] = lg[i >> 1] + 1;
    st[i][0] = a[i];
}
for(int j = 1;j <= lg[n];j++)
{
    for(int i = 1;i + (1 << j) - 1 <= n;i++)
    {
        st[i][j] = min(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
    }
}
int query(int l,int r)
{
    //#define len lg[r - l + 1];
    int len = lg[r - l + 1];
    return min(st[l][len],st[r - (1 << len) + 1][len]);
}

3. 更优秀的 RMQ#

因为 ST 表有个 $\Omicron(n \log n)$ 的预处理，在某些毒瘤的眼里还是太慢了，更何况还能套上线性基这种单次复杂度高达 $\Omicron(\log ^ 2 n)$ 的东西，于是我们可以用毒瘤之力打败毒瘤。

我们可以考虑对序列分块，处理块内的前后缀，再在块间建立一个 ST 表，每次我们可以将一个询问拆成三段，两边散块用处理好的前后缀，中间直接用块间的 ST 表。

好了现在该考虑块长了，设块长为 $B$。

预处理 ST 表的复杂度是 $\Omicron(t \frac{n}{B} \log _ 2\frac{n}{B}) = \Omicron(t (\frac{n}{B} \log n - \frac{n}{B} \log B))$，其中 $t$ 是单次合并复杂度。

$B = \log _ 2 n$ 时最优，查询是 $\Omicron(t)$ 的。