专栏文章

浅谈ST表

周周子衡
算法·理论参与者 57已保存评论 65

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
65 条
当前快照
1 份
快照标识符
@mhz5tlhu
此快照首次捕获于
2025/11/15 01:56
4 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文
先来一个小问题：
CPP
有N个数，M次询问，每次给定区间[L,R]，求区间内的最大值。

N<=10,M<=10
老师，我会O(N)O(N)暴力枚举！
再来：
CPP
N<=10^5,M<=10^5
老师，我会线段树O(log⁡N)O(\log N)处理每个询问！
再来：P3865 【模板】ST表
CPP
N<=10^5,M<=10^6
这时我们发现，随着MM的增大，O(log⁡N)O(\log N)的询问处理已经不够优秀，我们需要O(1)O(1)处理询问的方法。这就引出了我们今天的主题——ST\text{ST}表。

前置技能

倍增算法（例题：P3379 【模板】最近公共祖先（LCA））
区间动规（例题：P3146 [USACO16OPEN]248）

算法流程

我们现在要O(1)O(1)求出区间最大值，一个很自然的想法便是记录f(i,j)f(i,j)为[i,j][i,j]内的最大值，显然有转移方程f(i,j)=max⁡(f(i,j−1),aj)f(i,j)=\max(f(i,j-1),a_j)
但是这样预处理是O(N2)O(N^2)的，不能通过，我们考虑进一步优化
观察到一个性质：max⁡\max操作允许区间重叠，也就是max⁡(a,b,c)=max⁡(max⁡(a,b),max⁡(b,c))\max(a,b,c)=\max(\max(a,b),\max(b,c))（这个性质非常重要，决定了STST表是否能用来维护这种操作，例如STST表一般不能维护区间和，因为a+b+c≠a+b+b+ca+b+c\neq a+b+b+c），也就是我们可以由两个较小的、有重叠的区间直接推出一个大区间，因此我们可以少维护一些区间
计算机中有很多事物是跟22有关的。这里也是这样，我们采用倍增思想，令f(i,j)f(i,j)为从aia_i开始的、连续2j2^j个数的最大值，显然：
f(i,0)=aif(i,0)=a_i（显然根据定义可得）
f(i,j)=max⁡(f(i,j−1),f(i+2j−1,j−1)f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1)
这一条非常重要，我们画个图理解一下：
现在我们考虑f(1,2)f(1,2)，也就是[1,4][1,4]的最大值
我们把[1,4][1,4]分为了[1,2][1,2]和[3,4][3,4]两个小区间，这两个区间是我们之前求过的f(1,1)f(1,1)与f(3,1)f(3,1)，而f(1,1)=8,f(3,1)=7f(1,1)=8,f(3,1)=7，则f(1,2)=max⁡(f(1,1),f(3,1))=8f(1,2)=\max(f(1,1),f(3,1))=8
我们发现，在这种方式下，以每个点为起点都有O(log⁡N)O(\log N)个区间，每个区间可以O(1)O(1)求出，则预处理总时间、空间复杂度都为O(Nlog⁡N)O(N\log N)。
那怎么处理询问呢？
根据max⁡\max的性质，我们可以把区间拆成两个相重叠的区间。看图：
记询问区间长度为lenlen，我们从左端点向右找一段长为2log⁡(len)2^{\log(len)}的区间（蓝色部分），右端点向左也找一段长为2log⁡(len)2^{\log(len)}的区间（黄色部分），显然这两段区间已经覆盖了整个区间（中间重叠了一块绿色部分），取最大值即可
当然为了保证询问复杂度为O(1)O(1)，我们需要提前预处理出每个log⁡(len)\log(len)向下取整后的值。整个算法总时间复杂度为O(Nlog⁡N+M)O(N\log N+M)。
顺便附上代码：
CPP
#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];
    }
    
    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]);
        }
    }
    
    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
CPP
给定N个数和M个询问，求每次询问区间内极差=最大值-最小值。
用ST\text{ST}表求出区间最大值、最小值即可，最小值同理。（最小值也满足那个性质）
CPP
#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\text{ST}表还能维护很多东西，只要满足那条性质的静态问题都能维护，但ST\text{ST}表较难修改。
于是就有了这道新鲜出炉的省选题：（JSOIWC2019Day4T1JSOIWC2019Day4T1）
CPP
给定N个整数和M个询问，每次询问给定一个X，求有多少个区间[L,R]使得A[L]~A[R]的GCD为X。
算法1：
老师，我会暴力枚举每一个区间求GCDGCD！
复杂度：O(MN3log⁡A)O(MN^3\log A)
期望得分：00
算法2：（本蒟蒻的做法）
老师，我会把所有区间GCDGCD预处理出来，扔进mapmap里！
复杂度：O(N2log⁡N+Nlog⁡A+Mlog⁡N)O(N^2\log N+N\log A+M\log N)
期望得分：5050
算法3：
显然GCDGCD是满足上述性质的，因此可以用ST\text{ST}表求出每个区间最小值。
然后每个询问O(N2)O(N^2)枚举
接着我们发现，以每个数为起点的区间GCDGCD最多O(log⁡N)O(\log N)个（每次变化至少变小一半）
我们可以二分出第一次变化的点，记录出现次数，插入mapmap即可
复杂度：O(Nlog⁡2N+Nlog⁡Nlog⁡A+Mlog⁡N)O(N\log^2N+N\log N\log A+M\log N)
期望得分：100100

进阶

thanks to @xhhkwy
假设现在有个毒瘤出题人故意卡你……
CPP
有N个数，M次询问，每次给定区间[L,R]，求区间内的最大值。

N<=2*10^7,M<=2*10^7,随机数据，时限5s
然后发现……预处理都TT飞了
怎么办？我们要想方设法降低ST\text{ST}表的构造时间
分块都学过吧（没学过？出门左转P1903 [国家集训队]数颜色 / 维护队列）
让我们瞻仰一下@xhhkwy的仙气
CPP
将序列分成长度是logN的块，预处理出每一块的前缀min与后缀min，
然后在把每一个块的最小值拉出来跑st，
预处理时间复杂度为N + (N/logN)*log(N/logN) = O(N)，
询问的话如果两个端点在一个块中那么暴力，时间复杂度O(logN)。
否则直接查st表+前后缀min
（引自@xhhkwy私信）
各位自行理解吧，注意只有数据随机的情况才能使大部分查询操作复杂度为O(1)O(1)，如果题目没有写明“随机数据”则不要轻易使用

后记

本蒟蒻的ST\text{ST}表讲解到这里就结束了。希望大家已经掌握了这个算法。
点个赞呗

评论

共 65 条评论，欢迎与作者交流。

正在加载评论...