【模板】ST表

（那一天我唯一彻底搞懂的东西然而现在也忘光光）

先看题：（RP++）

先跳过暴力，这一题肯定不行的

这时就需要ST表，ST表：Sparse Table Algorithm

ST表分为两部分，预处理和查询。

预处理：

采用DP的思想，f[i][ j]表示[i , i+2^j - 1]区间中的最小值(也就是从第i个数起连续2j个数中的最小值)。

数列3,2,4,5,6,8,1,2,9,7。f[1][0]=3，f[1][1]=2，f[1][2]=2，f[1][3]=1，f[2][0]=2，f[2][1]=2，f[2][2]=2……

f[i][ j]可以由f[i][j-1]和f[i+2^j-1][ j-1]导出:

f[i][ j-1]表示区间[i , i+2^j-1-1]的最小值

f[i+2^j-1][ j-1]表示区间[i+2^j-1 , i+2^j-1+2^j-1-1]=[i+2^j-1, i+2^j-1] 的最小值 ,所以有DP方程：f[i][ j]=min(f[i][ j-1],f[i+2^j-1][ j-1])

这一部分都很好懂，接下来就是怎么查询了。

关于长度2解释：因为要完全覆盖整个区间，而对于求最大值和最小值两个区间有交集是没有影响的（不是精确覆盖），所以可以求2<=r-l+1

例题：（裸的ST表）

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[1000001];
int Fmax[100005][25];
int Fmin[100005][25];
int n,m;
void MM()
{
    for(int j=1;j<=floor(log(n)/log(2));j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            Fmax[i][j]=max(Fmax[i][j-1],Fmax[i+(1<<(j-1))][j-1]);
            Fmin[i][j]=min(Fmin[i][j-1],Fmin[i+(1<<(j-1))][j-1]);
}
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    Fmax[i][0]=a[i];
    Fmin[i][0]=a[i];
    }
    MM();
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int k=floor(log(y-x+1)/log(2));
        printf("%d\n",max(Fmax[x][k],Fmax[y-(1<<k)+1][k]));
    }
    return 0;
}

再看一道题？

（神奇矩阵）

大概思路：

（代码有时间再放吧。。要月考了。。。）

st表

【模板】ST表