数据结构之线性结构(完结)——ST表(稀疏表)

某次考试结束后，同学们在班级里比拼各自的考试成绩，很快每个小组的小组长都知道了自己组同学的最高分。

放学后，各名组长同学在跟父母聊天时，透露出本次考试时自己组同学的最高分，父母暗暗记下了分数。

晚上，家长群里，几位组长家长在群里分享出孩子所在组的最高分，一合计，就知道班级最高分是多少了。

上述情境中，家长们并不知道所有同学的成绩，只通过几个小组最高分的比较，就知道了整个班级的最高分，这就是本期将要介绍的ST表（Sparse Table）的应用。

ST表是一种简单的线性结构，主要用来解决静态的区间最值问题（RMQ问题，即Range Minimum/Maximum Query）。

RMQ问题，就是给定一个长度为n的数组，进行m次查询，每次查询区间[L,R]内的最值、极差、最大公约数等。这是一个具有“可重复贡献”性质的问题，即询问的区间存在重叠。

如果直接暴力搜索区间内的最值，其时间复杂度为O(mn)，在n和m的范围超过10000时效率会非常低。

而使用ST表可以在O(1)的时间复杂度查询到某区间的最值，但由于预处理ST表的时间复杂度为O(nlogn)，因此整体算法的时间复杂度也为O(nlogn)。

模拟生成ST表

前文的情境已经体现了ST表的核心：如果一个大区间能被多个小区间覆盖，那么大区间的最值，就是所有小区间的最值集合中的最值。

小区间的最值如何计算呢？它肯定又能被更小的2个或多个区间覆盖，再去求更小区间的最值。

不断递归拆分区间，直到区间里只有一个元素后，区间的最值就是元素自身，再往回计算递推回去。

以数组{9,3,1,7,5,6,0,8}为例，使用表格展示将区间一分为二求最小值的维护过程：

如果要求区间[5,8]的最小值，直接取第二个区间长度为4的最小值，即0；

但如果要求区间[2,5]的最小值，按照的表，需要取[2]、[3,4]、[5]这3个区间的最小值进行比较，然后得到答案为1，显然与直接遍历区间找最小值相比快不了多少。

因此，我们的表格需要改进，不能从大区间出发进行拆分，要从小区间开始，依次合并相邻两个区间来计算较大区间的最小值，最终计算出整个数组的最小值。

尽管是合并相邻区间，但是结合倍增法的优势，我们只需要计算长度为2的幂次方数的区间最值即可。最终改进后的区间维护表格如下：

在这张表格中，我们就能很快地找到区间[2,5]的最小值，也就是第二个区间长度4的值，即1。

如果要在这张表格里找区间[3,8]的最小值怎么办呢？我们可以让区间[3,6]和区间[5,8]的最小值，即第3和第5个区间长度为4的最小值作比较，两个区间的并集恰好是[3,8]。

这里我们可以发现，子区间的重合不影响大区间的结果，这也是ST表的适用场合。

同时，ST表是基于倍增法的算法。对倍增法不熟悉的读者，可以先跳转阅读之前的文章：

算法探秘——与“二分法”相反的算法：倍增法

ST表的建造与查询

1、建造ST表

根据上文分析，在使用ST表查询时，需要先建造和预处理ST表的数据。

结合倍增法的思想，我们定义st[i][j]为从第i个元素开始，长度为2^j的区间最小值（以下都以最小值为例）。

而在前面已经分析到了，长度为2^j的区间最小值，就是两个长度为2^(j-1)的区间最小值中的较小值。

其中，第一个长度2^(j-1)区间的起点为i，第二个长度2^(j-1)区间的起点为i+2^(j-1)，因此递推关系式可以写出：

st[i][j]=min(st[i][j-1], st[i+(1<<(j-1))][j-1])（注意，1<<(j-1)是2^(j-1)的位运算表示）

既然是递推关系，那就要思考边界条件。当j=0时，区间长度为1，区间的最值就是当前项的值。因此st数组的初始化代码可以这么编写：

for(int i=1;i<=n;i++){
  st[i][0]=a[i];
} 

接下来就是使用递推公式计算ST表各值了。这里有个小细节要思考：到底最长区间长度为2的几次方呢？

设最长长度是2的p次方，数组长度为n，需要满足下面的关系式：

使用数学中的log函数转换一下：

此时满足条件的最大整数p就对应着最长区间长度2^p。在C++的<cmath>库中有现成的log2(n)函数，可以帮助计算p值：

int p=log2(n); //int自动取整
for(int j=1;i<=p;j++){ //先枚举区间长度，从小到大 
      for(int i=1;i+(1<<k)-1<=n;i++){ //再枚举区间的左边界，要注意区间不能越界 
          st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); 
      }
}

循环需要进行

趟，每趟需要计算小于n次（第一趟为n-1次，第二趟为n-3次，第三趟为n-7次，以此类推），因此

总时间复杂度为O(nlogn)，并且计算量要小于nlogn。

上述寻找递推关系、边界条件的过程，其实也是在寻找最优子结构的过程，并且递推公式“无后效性”，因此ST表的递推关系其实是动态规划的过程。

动态规划是算法竞赛考察的“常客”，考验选手的问题分析与代码实现能力，会在之后单独开辟一个合集来详细介绍，敬请期待~

2、使用ST表查询

想要查询区间[L,R]的最小值，同样要先做一些数学分析。

区间的长度为len=R-L+1，由于len不一定是2的幂次方数，所以我们用两个小区间覆盖它时，需要有重复覆盖的部分。

设小区间的长度为x，需要x≤len且2*x≥len的区间长度能保证覆盖。例如len=21时，x=16的两个小区间就能覆盖。

因此，覆盖长度为len的区间，所需的2个小区间的长度为

。

最后注意，由于两个小区间会有重复覆盖的部分，因此右区间的起点不是左区间终点，而是由右区间的终点往前推，即起点为R-(1<<x)+1。

最终查询对应的代码如下：

int L,R;
cin>>L>>R;
int x=log2(R-L+1);
int ans=min(st[L][x],st[R-(1<<x)+1][x]);

接下来结合2道例题，带读者们去使用代码实现ST表的应用。

例题1：

ST 表 && RMQ 问题

算法解析

1、对于前30%的数据，我们先来试试看暴力求解，即题目给出一个区间，我们就遍历区间找出里面的最大值。时间复杂度为O(mn)。

参考代码：

#include<iostream>
using namespace std;
int a[100005];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        int ans=0;//题中保证数据都是非负数，因此极小值可以设为0 
        for(int i=l;i<=r;i++){
            ans=max(ans,a[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

评测结果：

2、后70%的数据，就要使用ST表来查询。由于前文已经非常详细地介绍了ST表的处理与查询过程，这里还请读者们阅读并理解完整版代码。

参考代码：

#include<iostream>
#include<cmath> 
using namespace std;
int a[100005];
int st[100005][20]; //区间长度最多为100000，小于2的17次方 
int n,m;
int l,r; 
int ans;
int main(){
    ios::sync_with_stdio(0); //加快cin、cout速度
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i][0]=a[i]; //输入的同时初始化st表边界情况 
    }
    //下面是预处理st表（题目是求区间最大值） 
    int p=log2(n); 
    for(int j=1;j<=p;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);//注意加减的运算优先级大于左移运算 
        }
    }
    //下面是使用st表进行m次查询 
    while(m--){
        cin>>l>>r;
        int x=log2(r-l+1); //计算小区间长度 
        ans=max(st[l][x],st[r-(1<<x)+1][x]);
        cout<<ans<<endl;
    }
    return 0;
}

评测结果：

这时候有读者要问了，明明已经用ST表来查询了，怎么还能超时呢？代码中还有优化的地方吗？还真有。

（1）将“endl”替换成’\n’。由于endl除了换行外还会清空缓冲区，因此速度比’\n’会慢很多；

（2）根据题干提示，使用快读的模版，会比cin的效率更高。关于快读的知识，在很早期的文章中就有介绍：

信息学奥赛的编程技巧（2）——提高输入速度

例题2：

忠诚

算法解析

将题干解读一下，发现要求的就是给定多个区间，求每个区间里的最小值，是一个经典的RMQ问题。

事实上，解决这类问题的算法不仅仅有ST表，还有线段树、树状数组、分块等多种做法。

在这些算法中，ST表所占的优势是算法和编码简单，并且查询的时间复杂度为O(1)，而线段树、树状数组查询的时间复杂度为O(logn)。

但是ST表要求数据是静态的，如果数组需要频繁维护，那么ST表就需要频繁更新，每次更新的时间复杂度都为O(nlogn)，就没有更新维护时间复杂度为O(logn)的线段树和树状数组快了。

回到本题，直接修改上一题的代码即可。这里加入了手动递推log2函数的各项整数值，读者们可以关注一下。由于<cmath>库中计算log2函数的结果是浮点数，因此会比自己递推计算log2整数要稍慢一点。

代码展示：

#include<iostream>
#include<cmath> 
using namespace std;
int st[100005][20]; //区间长度最多为100000，小于2的17次方 
int lg2[100005]; //手动计算各log2函数的值 
int m,n; //m笔帐，n个问题 
int l,r; 
int ans;
int main(){
    ios::sync_with_stdio(0);
    cin>>m>>n;
    lg2[1]=0;
    for(int i=2;i<=m;i++){
        lg2[i]=lg2[i>>1]+1; //基于对数函数性质的递推 
    } 
    for(int i=1;i<=m;i++){
        cin>>st[i][0]; //输入的同时初始化st表边界情况 
    }
    //下面是预处理st表，求区间最小值 
    int p=lg2[m];
    for(int j=1;j<=p;j++){
        for(int i=1;i+(1<<j)-1<=m;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); 
        }
    }
    //下面是使用st表进行n次查询 
    while(n--){
        cin>>l>>r;
        int x=lg2[r-l+1]; //计算小区间长度 
        ans=min(st[l][x],st[r-(1<<x)+1][x]);
        cout<<ans<<" ";
    }
    return 0;
}

总结

至此，奥赛大纲中数据结构的线性结构内容除了NOI级的“块状链表”外，入门级和提高级的知识点就全部介绍完啦~