ST表

学习了 ST表 这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。

什么是ST表

ST表的功能很简单:
它是解决RMQ问题(区间最值问题)的一种强有力的工具。
它可以做到预处理,查询最值(ohhhhhhhh)

实现

怎么做到的呢,它运用了倍增的思想。

拿最大值来说我们用表示,从位置开始的个数中的最大值,例如表示的是位置和位置中两个数的最大值(也就是说当前位置是被包含进个数去的)

那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值(注意这里的编号是从开始的)

transfer

查询的时候也比较简单
我们计算出,然后对于左端点和右端点分别进行查询,这样可以保证一定可以覆盖查询的区间

transfer

所以就有了这两个边界,,
至于为什么会是,你只要设左端点为, 并且满足, 然后就可以推出来了。

例题和代码

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

上代码

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
#include <bits/stdc++.h>
#define MaxN 100000 + 9
#define LogN 17 //顶多2的17次方就可以从左端到最右端了

using namespace std;

int f[MaxN][LogN], n, m;

inline int read() //快读 很容易暴毙
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
// x + (1 << len) - 1=r 草稿请无视🤣
int ask(int l, int r)
{
int len = log2(r - l + 1);
return max(f[l][len], f[r - (1 << len) + 1][len]); //关键,这样可以保证覆盖需要查询的区间
}

int main()
{
n = read(); m = read();
for (int i = 1; i <= n; ++i)
f[i][0] = read();//预处理的时候存在0的位置

for (int j = 1; j <= 21; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); //转移方程式
int a, b;
for (int i = 1; i <= m; ++i)
{
a = read(); b = read();
printf("%d\n", ask(a, b));
}
return 0;
}

嗯,没有四倍经验。
peace~

-------------本文结束,感谢您的阅读-------------