【洛谷日报#146】浅谈ST表

先来一个小问题：

有N个数，M次询问，每次给定区间[L,R]，求区间内的最大值。

N<=10,M<=10


老师，我会O(N)暴力枚举！

再来：

N<=10^5,M<=10^5

这时我们发现，随着M的增大，O(logN)的询问处理已经不够优秀，我们需要O(1)处理询问的方法。这就引出了我们今天的主题——ST表。

我们现在要O(1)求出区间最大值，一个很自然的想法便是记录f(i,j)为[i,j]内的最大值，显然有转移方程f(i,j)=\max(f(i,j-1),a_j)

但是这样预处理是O(N^2)的，不能通过，我们考虑进一步优化

观察到一个性质：max操作允许区间重叠，也就是max(a,b,c)=max(max(a,b),max(b,c))（这个性质非常重要，决定了ST表是否能用来维护这种操作，例如ST表一般不能维护区间和，因为a+b+c\neq a+b+b+c），也就是我们可以由两个较小的、有重叠的区间直接推出一个大区间，因此我们可以少维护一些区间

计算机中有很多事物是跟2有关的。这里也是这样，我们采用倍增思想，令f(i,j)为从a_i开始的、连续2^j个数的最大值，显然：

f(i,0)=a_i（显然根据定义可得）

f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1)

这一条非常重要，我们画个图理解一下：

现在我们考虑f(1,2)，也就是[1,4]的最大值

我们把[1,4]分为了[1,2]和[3,4]两个小区间，这两个区间是我们之前求过的f(1,1)与f(3,1)，而f(1,1)=8,f(3,1)=7，则f(1,2)=max(f(1,1),f(3,1))=8

我们发现，在这种方式下，以每个点为起点都有O(logN)个区间，每个区间可以O(1)求出，则预处理总时间、空间复杂度都为O(NlogN)。

那怎么处理询问呢？

根据\max的性质，我们可以把区间拆成两个相重叠的区间。看图：

记询问区间长度为len，我们从左端点向右找一段长为2^{log(len)}的区间（蓝色部分），右端点向左也找一段长为2^{log(len)}的区间（黄色部分），显然这两段区间已经覆盖了整个区间（中间重叠了一块绿色部分），取最大值即可

当然为了保证询问复杂度为O(1)，我们需要提前预处理出每个log(len)向下取整后的值。整个算法总时间复杂度为O(NlogN+M)。

顺便附上代码：

#include<cstdio>
#include<algorithm>

using namespace std;

int a[100001]={};
int lg[100001]={-1};
int maxn[100001][50]={};

int main()
{
    int n=0,m=0;
    scanf('%d%d',&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf('%d',&a[i]);
        lg[i]=lg[i/2]+1;
    }
    for(int i=1;i<=n;i++)
    {
        maxn[i][0]=a[i];
    }
    //puts('OK');
    for(int i=1;i<=lg[n];i++)
    {
        for(int j=1;j+(1<<i)-1<=n;j++)
        {
            maxn[j][i]=max(maxn[j][i-1],maxn[j+(1<<(i-1))][i-1]);
        }
        //puts('OK');
    }
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;i+(1<<j)-1<=n;j++)
        {
            printf('%d ',maxn[i][j]);
        }puts('');
    }*/
    int l=0,r=0;
    while(m--)
    {
        scanf('%d%d',&l,&r);
        int len=lg[r-l+1];
        printf('%d\n',max(maxn[l][len],maxn[r-(1<<(len))+1][len]));
    }
    return 0;
}

应用

先来一道模板题：P2880 [USACO07JAN]平衡的阵容Balanced Lineup

给定N个数和M个询问，求每次询问区间内极差=最大值-最小值。


用ST表求出区间最大值、最小值即可，最小值同理。（最小值也满足那个性质）

#include<cstdio>
#include<algorithm>

using namespace std;

int a[100001]={};
int lg[100001]={-1};
int maxn[100001][50]={};
int minn[100001][50]={};

int main()
{
    int n=0,m=0;
    scanf('%d%d',&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf('%d',&a[i]);
        lg[i]=lg[i/2]+1;
        maxn[i][0]=a[i];
        minn[i][0]=a[i];
    }
    for(int i=1;i<=lg[n];i++)
    {
        for(int j=1;j+(1<<i)-1<=n;j++)
        {
            maxn[j][i]=max(maxn[j][i-1],maxn[j+(1<<(i-1))][i-1]);
            minn[j][i]=min(minn[j][i-1],minn[j+(1<<(i-1))][i-1]);
        }
    }
    int l=0,r=0;
    while(m--)
    {
        scanf('%d%d',&l,&r);
        int len=lg[r-l+1];
        printf('%d\n',max(maxn[l][len],maxn[r-(1<<len)+1][len])-
        min(minn[l][len],minn[r-(1<<len)+1][len]));
    }
    return 0;
}

当然，ST表还能维护很多东西，只要满足那条性质的静态问题都能维护，但ST表较难修改。

于是就有了这道新鲜出炉的省选题：（JSOI2019Day4T1）

给定N个整数和M个询问，每次询问给定一个X，求有多少个区间[L,R]使得A[L]~A[R]的GCD为X。


算法1：

老师，我会暴力枚举每一个区间求GCD！

复杂度：O(MN^3logN)

期望得分：0

算法2：（本蒟蒻的做法）

老师，我会把所有区间GCD预处理出来，扔进map里！

复杂度：O(N^2logN+MlogN)

期望得分：50

算法3：

显然GCD是满足上述性质的，因此可以用ST表求出每个区间最小值。

然后每个询问O(N^2)枚举

接着我们发现，以每个数为起点的区间GCD最多O(logN)个（每次变化至少变小一半）

我们可以二分出第一次变化的点，记录出现次数，插入map即可

复杂度：O(Nlog^2N+MlogN)

期望得分：100

假设现在有个毒瘤出题人故意卡你……

有N个数，M次询问，每次给定区间[L,R]，求区间内的最大值。

N<=2*10^7,M<=2*10^7,随机数据，时限5s

然后发现……预处理都T飞了

怎么办？我们要想方设法降低ST表的构造时间

将序列分成长度是logN的块，预处理出每一块的前缀min与后缀min，
然后在把每一个块的最小值拉出来跑st，
预处理时间复杂度为N + (N/logN)*log(N/logN) = O(N)，
询问的话如果两个端点在一个块中那么暴力，时间复杂度O(logN)。



各位自行理解吧，注意只有数据随机的情况才能使大部分查询操作复杂度为O(1)，如果题目没有写明“随机数据”则不要轻易使用

后记

本蒟蒻的ST表讲解到这里就结束了。希望大家已经掌握了这个算法。