首页 > 其他分享 >ST表学习笔记

ST表学习笔记

时间:2022-12-28 09:44:16浏览次数:67  
标签:log max 笔记 st 学习 区间 ST dp

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)\) 不支持 不支持

不难看出,线段树从综合上来看是更厉害的,不过如果只有 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 表

思路:

模板题,放一下代码。

代码:

#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 表,不过我们这次需要对预处理的区间记录以下几个信息:

\(ans\):这段区间的答案。

\(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)\) 的时间复杂度内求出来了。

代码:提交记录


标签:log,max,笔记,st,学习,区间,ST,dp
From: https://www.cnblogs.com/rlc202204/p/17009458.html

相关文章