ST表学习笔记

· · 个人记录

RMQ问题

RMQ（Range Minimum/Maximum Query）问题是指多次查询某个范围内的最大最小值（或极值），比如对一个序列多次查询区间的最大最小值。

设范围内共有 n 个元素，查询 m 次。

朴素算法：

遍历所有范围内的元素，再取最大或最小，则单次查询时间复杂度最 坏为 O(n)，总时间复杂度最坏为：O(nm)，还是太慢了。

于是就有无数的牛人发明了各种用于 RMQ 问题算法，并且有些算法是可以做到区间修改的，下面这张表格看一下：

算法 预处理 单次查询 单点修改 区间修改
朴素算法 无 O(n) O(1) O(n)
分块 O(n) O(\sqrt{n}) O(\sqrt{n}) O(\sqrt{n})
线段树 O(n) O(\log{n}) O(\log{n}) O(\log{n})
树状数组 O(n) O(\log{n}) O(\log{n}) 结合差分可以做到 O(\log{n})
ST 表 O(n \log n) O(1) O(n) 不支持

不难看出，线段树从综合上来看是更厉害的，不过如果只有 RMQ， 那么 ST 表是最厉害的。

ST 表

思想

我们设这个序列是 a_1,a_2,a_3,...,a_n。

我们可以预处理出所有长度为 2^i 的长度的区间的答案，比如对于一个长度为 10 的区间，我们需要预处理出下图所有彩色区间的最大值：

其中橙色的区间是所有长度为 2 的区间，蓝色是所有长度为 4 的区间，绿色是所有长度为 8 的区间。

我们设 st_{i,j} 为以 i 开头，长度为 2^j 的区间的最大值，于是在上图中我们发现，两个相邻的橙色区间可以合并成一个蓝色区间，两个相邻的蓝色区间可以合并成一个绿色区间，于是我们就得到了 st_{i,j} 的递推式：

st_{i,0}=a_i st_{i,j}=\max\{st_{i,j-1}, st_{i+2^{j-1},j-1}\}

这样的预处理时间和空间复杂度都是 O(n \log n) 的，因为总共有 n \log n 个需要预处理的区间。

所以我们费了这么大劲搞出来一个东西有什么用呢？ST 表可以做到 O(1) 查询。

举个例子，假设我们要查询第 3 到 8 这段区间的最大值，那么我们需要两个长度不比 (8-3+1)=6 大中最大的 2 的幂，且这两个区间能覆盖 [3,8]。如下图：

黑色区间就是我们选择的区间，长度为 4，其实就是 2^{\lfloor \log_2(8-3+1)\rfloor}=2^{\lfloor \log_2(6)\rfloor}=2^2 ，于是对于区间 [l,r] 来说，我们设 k = \lfloor \log_2(r-l+1)\rfloor, 答案就是：\max\{st_{l,k}, st_{r-2^k+1,k}\}，这样查询就是 O(1) 的了。

实现

预处理

我们设 pw_i=2^i，lg_i=\lfloor \log_2(i)\rfloor，于是我们就可以写出预处理代码：

void init() {
    lg[1] = 0, pw[0] = 1;
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    for (int i = 1; i <= 20; i++)
        pw[i] = pw[i - 1] * 2;
    for (int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for (int j = 1; pw[j] <= n; j++)
        for (int i = 1; i + pw[j] - 1 <= n; i++)
            st[i][j] = max(st[i][j - 1], st[i + pw[j - 1]][j - 1]); 
}

查询

按照我们之前说过的方法直接查询即可：

int qry(int l, int r) {
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - pw[k] + 1][k]);
}

ST 表中的单点修改

ST 表可以进行 O(n) 的单点修改。我们只需要修改包含这个点的所有区间即可。

包含这个点的且长度为 2^x 次方的区间 2^x 个级别，所以总共需要修改约 \sum_{i=0}^{\log n}2^i=2^{\log n+1}-1 次，也就是 O(n)。

一些题目

题目名 【模板】ST 表

题目链接：【模板】ST 表

思路：

模板题，放一下代码。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXN_LOG = 20; 
int st[MAXN][MAXN_LOG] = {{0}};
int a[MAXN] = {0}, lg[MAXN] = {0}, pw[MAXN_LOG] = {0}, n, m;
void init() {
    lg[1] = 0, pw[0] = 1;
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    for (int i = 1; i <= 20; i++)
        pw[i] = pw[i - 1] * 2;
    for (int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for (int j = 1; pw[j] <= n; j++)
        for (int i = 1; i + pw[j] - 1 <= n; i++)
            st[i][j] = max(st[i][j - 1], st[i + pw[j - 1]][j - 1]); 
} 
int qry(int l, int r) {
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - pw[k] + 1][k]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]); 
    init();
    for (int i = 1, l, r; i <= m; i++) {
        scanf("%d%d", &l, &r);
        printf("%d\n", qry(l, r));
    }
    return 0;
}

[USACO07JAN] Balanced Lineup G

题目链接：[USACO07JAN] Balanced Lineup G

思路：

挺没意思的一道题，记录最大和最小值即可。

代码：提交记录

gcd区间

题目链接：gcd区间

思路：

我们可以把去 ST 表中取最大的操作改成取 \gcd，这样就可以过了。

代码：提交记录

玉米地

题目链接：玉米地

思路：

这里涉及到二维 ST 表。

ST 表也可以是二维的，我们设 st_{i,j,k} 表示左上角位置为 (i,j) ，边长为 2^k 的正方形中的最大值（最小值同理，最后相减即可，这里只说最大值），对于 st_{i,j,k}，我们可以这样更新：

st_{i,j,k}=\max\{ st_{i,j,k-1}, st_{i,j+2^k,k}, st_{i+2^k,j,k}, st_{i+2^k,j+2^k,k}\}

我们通过这张图直观感受一下：

这就是初始化，这样的时间复杂度是 O(n^2\log n)。

查询操作大同小异，我们依然是找到不比边长大中最大的 2 的幂。设我们要找左上角为 (i,j)，边长为 len 的正方形中的最大值，我们设 k=\lfloor \log_2(len)\rfloor，答案就是：

\max\{ st_{i,j,k}, st_{i,j+len-2^k,k}, st_{i+len-2^k,j,k}, st_{i+len-2^k,j+len-2^k,k}\}

再来一张图直观感受一下：

其实只要有图就好理解了，于是我们就掌握了二维 ST 表。

但这道题有个问题，询问有可能出界，于是我们预处理是直接把边长乘 2，然后把所有不在界里的都设成无穷大或无穷小即可。

代码：提交记录

[JSOI2008] 最大数

题目链接：[JSOI2008] 最大数

思路：

这道题如果不强制在线，我们完全可以离线，等所有数都加完了再去处理询问，但是这道题强制在线，所以我们需要想办法让 ST 表支持修改。

我们发现，如果在末尾新增一个元素，那么所有长度为 2 的幂次方，且末尾为这个元素的都需要更新。但这是新的末尾，所以其实我们之前并没有记录过以上区间的答案，于是我们可以通过查询直接记录即可。由于最多只需要更新 \log(n) 个区间，所以修改是 O(\log n)，查询是 O(1) 的。

具体怎么更新，我们假设新的末尾是第 n 个元素，那么对于某个 k 满足 2^k \le n，st_{n-2^k+1,k}=\max\{\max\limits_{n-2^k+1\le i\le n-1}\{a_i\},a_n\}，而 \max\limits_{n-2^k+1\le i\le n-1}\{a_i\} 可以 O(1) 算出来，于是更新一个值也是 O(1) 的。

代码：提交记录

FREQUENT - Frequent values

题目链接：FREQUENT - Frequent values

思路：

一道有趣的题目，首先我们要求的依然是极值，所以依然可以用 ST 表，不过我们这次需要对预处理的区间记录以下几个信息：

$pre$：这段区间所有数都相同的最长前缀长度。 $suf$：这段区间所有数都相同的最长后缀长度。 $l$：这段区间的左端点。 $r$：这段区间的右端点。 $len$：这段区间的长度。（其实通过 $l,r$ 也能直接推出来） 初始化时，把相邻的且长度相同的两个区间合并成一个时，设小区间叫 $x$ 和 $y$，则大区间应该这么变： 1) 大区间的 $l=x.l,r=x.r,len=x.len+y.len$。 2) 若 $a_{x.r}=a_{y.l}$，则 $ans=\max\{x.ans,y.ans,x.suf+y.pre\}$； 否则 $ans = \max\{x.ans,y.ans\}$.。 3) 若 $a_{x.l}=a_{y.l}$，则 $pre=x.len+y.pre$；否则 $pre=x.pre$。 4) 若 $a_{x.r}=a_{y.r}$，则 $suf=y.len+x.suf$；否则 $suf=y.suf$。 这样依然可以在 $O(n \log n)$ 的时间里完成预处理。 考虑查询时，我们还是设 $k=\lfloor \log_2(r-l+1)\rfloor$，然后分以下两种情况讨论： 1) 若重叠部分的数全部相同，那么答案就是 $\max\{st_{l,k}.ans,st_{r-2^k+1,k}.ans,[{st_{l,k}.suf+st_{r-2^k+1,k}.pre-2^{k+1}+(r-l+1)}]\}

2) 否则答案是：\max\{st_{l,k}.ans,st_{r-2^k+1,k}.ans\}

代码：提交记录

Strip

题目链接：Strip

思路：

这道题很有意思，我们一步一步来。

首先这道题很明显时不能贪心的，于是我们考虑动态规划。我们设 dp_i 表示前 i 个元素能分成的最小段数，那么最朴素的更新就是枚举最后选的一段，我们可以用 ST 表 O(1) 查询极差判断是否能选，于是就有：

dp_i=\min\{dp_j+1\}(1 \le j < i,i - j \ge L,\max_{j < k\le i}{a_k}-\min_{j<k\le i}{a_k} \le s)

但这样是 O(n^2) 的，考虑如何优化。

我们发现，当一个区间越来越长，极差单调不降。原因很简单，因为最大值不会变小，最小值不会变大，而极差等于最大值减最小值，于是极差单调不降。

这个有什么好处呢？这就意味着以 i 结尾的那一段的长度大于等于 L，同时也会小于等于某个数，因为极差有上限。所以我们要找到 i 之前第一个使得以 i 结尾的段极差小于等于 s 的。举个列子，像下图这样：

Dif 就是极差的意思，在上图中，真正能去影响 dp_i 的是 dp_{i-2} 到 dp_{i-4}，dp_{i-1} 长度不够，dp_{i-5} 往前极差太大，所以：

dp_i=\min\{dp_{i-2},dp_{i-3},dp_{i-4}\}+1

一般化，我们设 cur 为能影响 dp_i 的下标中最小的一个，那么其实 dp_i 就是 \min\limits_{cur \le j\le i-L}\{dp_j\} +1。

我们进一步发现对于每个 i 来说，cur 也是不降的，于是我们可以搞一个指针指向 cur，每次向右移动，最多移动 n 次，所以时间复杂度是 O(n) 的。

再考虑如何求 \min\limits_{cur \le j\le i-L}\{dp_j\}，这不就是一个 RMQ 吗？而且每次我们会往 dp 数组末尾加一个元素，而 ST 表刚好支持 O(\log n) 的末尾添加元素，所以我们在搞一个维护 dp 数组最小值的 ST 表即可。

这道题大致思路就是这样，最终时间复杂度是 O(n \log n) 的。不过实现是还是有很多细节需要注意。

代码：提交记录

Friends and Subsequences

题目链接：Friends and Subsequences

思路：

这道题也是很有意思的一道题。首先朴素的做法肯定是枚举区间，然后用 ST 表进行 O(1) 判断。但是复杂度是 O(n^2) 的。

我们首先要想到固定一个边界。即，我们去枚举所有 l，尝试去用 O(\log n) 的时间复杂度算出有多少 r 满足题目的限制。我们拿个序列研究一下，当 n=6，a=1,2,3,2,1,4;b=6,7,3,3,1,2, 以 l=1 时为例：

其中相差指的是 \max\limits_{i=l}^ra_i-\min\limits_{i=l}^rb_i 的值，不难发现，这个值时单调不降的，于是这就促使我们可以去二分这个值等于 0 使得最小的 r 和 最大的 r，他们之间（包括自己）各自与 l 组成的区间都是满足条件的区间，于是这道题我们就可以在 O(n \log n) 的时间复杂度内求出来了。

代码：提交记录