Hunter'sBlog

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

什么是ST表

ST表的功能很简单：
它是解决RMQ问题(区间最值问题)的一种强有力的工具。
它可以做到$O(nlogn)$预处理，$O(1)$查询最值（ohhhhhhhh）

实现

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

拿最大值来说我们用$Max[i][j]$表示，从$i$位置开始的$2^j$个数中的最大值，例如$Max[i][1]$表示的是$i$位置和$i+1$位置中两个数的最大值(也就是说当前位置是被包含进$2^j$个数去的)

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

transfer

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

transfer

所以就有了这两个边界，$[l,l+2^k-1]$, $[r-2^k+1,r]$
至于为什么会是$[r-2^k+1,r]$，你只要设左端点为$x$, 并且$x$满足$x + 2^k - 1 = r$, 然后就可以推出来了。

例题和代码

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

上代码

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~

评论