什么，RMQ问题你还是只会线段树？什么，区间最值有1e7个查询，O(nlogn)卡不过去？没事，这篇BLOG，就让我们一同学习RMQ[区间最值]问题的另一个大杀器——ST表。

什么是ST表

ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到O(nlogn)的预处理，O(1)的单次查询，速度吊锤隔壁的线段树。别看名字很高级，其思路其实就是我们所熟悉的倍增思想(比如哆啦A梦的倍增液)。

实现方法

其实ST算法主要分成两大块，预处理和查询，下面就以求取区间最大值为例子，让我来为你一一进行讲解吧。

前期准备

由于再运算过程中，我们可能要多次求解 2^i 和 log i ，所以为了方便后续处理，我们先预处理出两个数组bin[i]:表示2^i等于多少；logg[i]，表示log i的整数部分是多少，处理也非常简单，直接贴上代码：

    bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]*2;
    logg[0]=-1;for(int i=1;i<=n;i++)logg[i]=logg[i/2]+1;

预处理部分

我们先开辟一个数组f[i][j]表示从第i号节点到第i+2^j-1号节点的最大值，即从i号节点开始往后数共2^j个节点中的最大值。

例如f[i][1]指的就是 第i号节点 和 第i+1号节点 的最大值。

但是暴力的来构造肯定是不行的呀，我们考虑利用性质进行二分。我们可以逐层循环j和i，当我们循环到要处理f[i][j]时，我们其实就是要求这个蓝色区间中的最大值：

这时我们发现，由于区间长度为2^j,所以是可以分割成左右两部分的，如下图：

所以我们蓝色区间的最大值就等于紫色和粉色区间最大值中的最大值。所以这里就运用倍增思想，巧妙地进行了预处理，具体的代码如下：

for(int i=1;i<=logg[n];i++)
    for(int j=1;j<=n;j++)
    {
        if(j+bin[i]-1<=n)
        {
            a[j][i]=my_max(a[j][i-1],a[j+bin[i-1]][i-1]);
        }
    } 

最值查询部分

首先，我们要先明白一个定理：2^log(x)>x/2,这个定理有什么用呢？这个定理就是告诉我们，任意一个长度为x的区间，都能被两端长度为2^log(x)的区间所覆盖，如下图：

所以我们的查询也变得很简单了，假如我们要查询区间[x,y]的最大值，很显然，这段区间长度t=y-x+1；那么我们只要求出以x为首，长度为2^log(t)的区间的最大值 和 以y为尾，长度为2^log(t)的区间的最大值，就一定包括了整个区间的最大值，如下图：

所以我们可以知道 [x,y] 中的最大值为 max(f[x][log t],f[y-2^log t+1][log t]);。

具体代码如下：

scanf("%d%d",&x,&y);
t=y-x+1;lg=logg[t];
printf("%d\n",my_max(a[x][lg],a[y-bin[lg]+1][lg]));

模板&模板题

[luogu P3865]【模板】ST表

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

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

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

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

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

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

输出格式：
输出包含 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

这就是一个经典的ST表模板了，没什么好说的，直接上板子QwQ：

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int a[110000][30],logg[110000],bin[110000];
int i,j,k,m,n,o,p,js,jl,x,y,t,lg;
int my_max(int x,int y)
{
    if(x>y)return(x);
    else return(y);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i][0]);

    bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]*2;
    logg[0]=-1;for(int i=1;i<=n;i++)logg[i]=logg[i/2]+1;

    for(int i=1;i<=logg[n];i++)
    for(int j=1;j<=n;j++)
    {
        if(j+bin[i]-1<=n)
        {
            a[j][i]=my_max(a[j][i-1],a[j+bin[i-1]][i-1]);
        }
    } 

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        t=y-x+1;lg=logg[t];
        printf("%d\n",my_max(a[x][lg],a[y-bin[lg]+1][lg]));
    }

    return 0;
}

结语

通过这篇BLOG，我们一起学会了ST表，你也终于学会用ST表解决部分RMQ问题了，你也学会如何水过区间最值有1e7个查询了。总而言之，ST表还是一个很好学很好用的数据结构的，还是需要勤加练习来体会其中的思想，特别是倍增算法。最后希望你喜欢这篇BLOG！