ST表浅析

发表于
字数统计: 2,268 | 阅读时长 ≈ 10

前言

很久没有写博客了
水一波~~~

ST表

我们来介绍一种O（1）求RMQ的算法
如果我们使用树状数组或者线段树等数据结构是可以在 log 的级别下求出区间最值的
看样子ST表很优越？！时间复杂度很优越？！
我们来看一下ST表的特点…

  • ST表不支持在线修改，只能求解RMQ问题
  • ST表预处理的时间复杂度为O（nlogn），查询时间为O（1）
  • ST表基于类似于DP和二进制的思想
  • 所以我瞎扯不出别的内容了…

我们用 mn[i][j] 表示从 i 到 i + 2j-1 的长度，在进行状态转移时，我们把长度为 2j 的区间分成两等分，每份的长度均为 2j-1，这两个区间的最值就是我们要求的区间和
转移方程为 mn[i][j]=min(mn[i,j-1],mn[i][i+2j-1-1])
关于具体的证明就不在这里阐释了，转移的过程上面已经给出了，我觉得很好理解…
同样最大值也是类似转移

我们来看一下代码（f 表示最大值，g表示最小值

1
2
3
4
5
6
7
8
9
inline void init(){
	for(re i=1;i<=n;i++)
		f[i][0]=g[i][0]=a[i];
	for(re j=1;(1<<j)<=n;j++)
		for(re i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
		}
}

然后我们看一下询问操作

在预处理的时候，每一个区间对应的长度都是 2i，但是每次查询的长度不一定是 2i 的，这该怎么办呢…
我们把查询的区间分成两部分，使这两个区间能够覆盖我们要求的区间，其次，这两个区间的长度应该都等于 2i 能够满足预处理的结果
分成的两个区间重合也没关系，因为我们求的是区间最值…
我们可以直接得到上述的 i ，对区间长度取以 2 为底的对数即可
因此，我们把待查区间（a,b）分成(a,a+2i-1）和 （b-2i+1,b）即可，对（a,b）区间取最大（最小）值，即在分成的两个区间中取max（min）即可，由于我们已经进行了预处理，所以这一次的时间复杂度为O（1），即每次查询的时间复杂度为O（1）
我们来看一下代码

1
2
3
4
5
6
7
inline int rmq(int x,int y){
	int k=0;
	while((1<<(k+1))<=y-x+1) k++;
	int ans1=max(f[x][k],f[y-(1<<k)+1][k]);//加1
	int ans2=min(g[x][k],g[y-(1<<k)+1][k]);//加1
	return ans1-ans2;
}

我们用 while 找对数，实际上也可以用 < cmath > 库

模板题

题目背景

这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1) O(1)

题目描述

给定一个长度为 N N 的数列，和 M M 次询问，求出每一次询问的区间内数字的最大值。

输入输出格式

输入格式：

第一行包含两个整数 N,M ，分别表示数列的长度和询问的个数。

第二行包含 N 个整数（记为 ai），依次表示数列的第 i 项。

接下来 M 行，每行包含两个整数 li,ri，表示查询的区间为 [li,ri]

输出格式：

输出包含 M 行，每行一个整数，依次表示每一次询问的结果。

输入输出样例

输入样例#1：
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
输出样例#1：
9
9
7
7
9
8
7
9

说明

对于30%的数据，满足： 1≤N,M≤10

对于70%的数据，满足： 1≤N,M≤105

对于100%的数据，满足： 1≤N≤105,1≤M≤106,ai∈[0,109],1≤li≤ri
≤N

解题思路

我能说拉题目的的时候，我要改很久吗…
我开始写了一个裸的线段树，但是分数不是很好看…
题面已经提醒了，每次询问要O（1）
询问的次数很多，log 级别的复杂度 T 得飞起
所以我们另辟蹊径，来用ST表解题
ST表虽然看样子解RMQ问题很优越但是它并不支持修改，所以能用的地方很少，局限性很大
所以我们就用裸的ST表跑的飞快…
思路上面都讲了核心代码也给出了（也就这么点…我觉得变化不会很大

AC代码1476ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<cstring>
#include<cmath>
#define max(a,b) (a>b?a:b)
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

const int N=100010;
int n,m,l,r;
int s[N],f[N][100];

inline void init(){
    rep(i,1,n) f[i][0]=s[i];
    int t=log(n)/log(2)+1;
    rep(j,1,t-1) rep(i,1,n-(1<<j)+1) f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}

inline int query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&s[i]);
    init();
    while(m--){
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }
    return 0;
}

我觉得这个算法变化也不大不信你看下面这道题

BZOJ1699

Description

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.

Input

  • 第一行: N 和 Q. * 第2..N+1行: 第i+1行是第i头牛的身高.

    • 第N+2..N+Q+1行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从A到B的所有牛.

Output

*第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0

解题分析

题目的意思就是求区间的最大和区间的最小…
好像很多人用树状数组或者线段树就能跑还跑的飞快？
没事我们老老实实用ST表发一波题解…
ST表支持的是求区间最大和区间最小，用到这道题刚刚合适
所以我们在 nlogn 的时间复杂度下预处理再 O（1） 地查询，岂不美哉？
我们只需要预处理出最大值和最小值即可，也就是把 ST表 预处理最大和最小值相结合
简单的我都不知道该口糊什么了…
以下的代码 f 表示的是最大值的预处理，g 表示的是最小值的预处理…
所以裸的模板也没有什么注释好加（注意边界进行加 1…
说实在话ST表也没有什么变式的因为自身的局限性我觉得一般的比赛中题目也很少（也就只能就静态区间的最值…

AC代码352ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register int

using namespace std;

const int N=50010;
int n,q,a[N];
int f[N][20],g[N][20];

inline void init(){
    for(re i=1;i<=n;i++)
        f[i][0]=g[i][0]=a[i];
    for(re j=1;(1<<j)<=n;j++)
        for(re i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
        }
}

inline int rmq(int x,int y){
    int k=0;
    while((1<<(k+1))<=y-x+1) k++;
    int ans1=max(f[x][k],f[y-(1<<k)+1][k]);
    int ans2=min(g[x][k],g[y-(1<<k)+1][k]);
    return ans1-ans2;
}

int main(){
    scanf("%d%d",&n,&q);
    for(re i=1;i<=n;i++) scanf("%d",&a[i]);
    init();
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",rmq(x,y));
    }
    return 0;
}

的确有人说树状数组和线段树跑得过ST表…
还是说我人丑常数大？

后记

意义不大？！
虽然ST表很简单但是…学一点总好
即使我觉得用处不是很广
学一学还是很简单的这东西核心就是一个预处理的DP…
很久没有写博客了补一发…
的确是最近几天没有什么好的题材都去划水了…

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan

要联系加我！！！（欢迎指正…