ST表

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

什么是ST表

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

实现

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

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

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

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

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

例题和代码

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

上代码

#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~