浅谈ST表及其离（谱）线操作

· · 个人记录

本篇博客适合学过位运算和二维数组的同学。

零、最值

废话少说，给题，上代码。

P5718

#include <iostream>
using namespace std;
int a[10005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int mn=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
            mn=min(mn,a[i]);
    }
    cout<<mn;
    return 0;
 }

这个题都不会的去看题解，我不讲弱智题

可以看到，这个题共有1次询问，数组长度为n，上述解法空间复杂度是O(n)，时间复杂度是O(qn)，其中q=1。

接下来步入正题。

P3865模板题

P1440离线题

一、多次查询最值暴力解法

直接上代码了，没什么好讲的。

 //P3865
#include <iostream>
using namespace std;
int a[10005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    while(m--){
      int mx=0,l,r;
      l=read();r=read();
      for(int i=l;i<=r;i++){
          mx=max(mx,a[i]);
      }
      printf("%d\n",mx);
    }
    return 0;
 }

空间复杂度是O(n)，时间复杂度是O(qn)。

二、多次查询全部预处理解法

我们可以看到，之所以这道题会严重超时，在于每次计算最大值时遍历了区间内的所有数字。如果我们在预处理时把答案存下来，时间复杂度的瓶颈就在于预处理了。时间复杂度O(n^2+q)。代码：

 //P3865
#include <iostream>
using namespace std;
int a[1005],f[1005][1005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=read();
        for(int j=1;j<=i;j++){
              f[j][i]=max(f[j][i-1],a[i]);
        }
    }
    while(m--){
      int l,r;
      l=read();r=read();
      printf("%d\n",f[l][r]);
    }
    return 0;
 }

三、倍增拆分

可以看到以上代码预处理时间太长。考虑将数组切割成多段，将每段取最大值。

如何切割呢？一般的思路都是将数组切成一些长度为2的整数次幂的子串。我们可以预处理所有长度为2的整数次幂的子数组的最大值。设f_{i,j}表示以i开头，长度为2^j的子数组的最大值。对于该算法我们只给出预处理部分，其余部分请读者自行完成或直接放弃。时间复杂度O(qlogn)


    for(int i=1;i<=n;i++){
        f[i][0]=a[i];
    }
    for(int j=1;j<=log[n];j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        } 
    }

另外，此处需要想办法求出log_2 n向下取整的结果。这里只给出状态转移方程f_i=f_{i/2}+1。具体实现见下文。这里的除法是整除。

四、ST表

可以看出，求最大值时不需要恰好每个数只求一次。哪怕一个数被求了2次，结果也是正确的，这就是求最值的可重复贡献性。所以我们可以把一个区间拆成两个重叠的区间。我们在求某个区间的最大值时只需要求其以左端点开头的和以右端点结尾的两个重叠的，长度为2的整数次幂的区间即可。我们可以轻松地得到这两个区间。时间复杂度O(q+nlogn)，空间复杂度O(nlogn)。代码如下：

 //P3865
 #include<iostream>
#include<cmath>
using namespace std;
int n,f[1000050][22],a[1000050],cpL[1000050];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void pre(){
    for(int i=1;i<=n;i++){
        f[i][0]=a[i];
    }
    for(int j=1;j<=cpL[n];j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        } 
    }
}
int main(){
    int q;
    n=read();q=read();
    cpL[0]=-1;
    for(int i=1;i<=n;i++){
        a[i]=read();
        cpL[i]=cpL[i/2]+1;
    }
    pre();
    while(q--){
        int x,y;
        x=read();y=read();
        int m=cpL[y-x+1];
        printf("%d\n",max(f[x][m],f[y-(1<<m)+1][m]));
    } 
    return 0;
}

五、离谱线操作

离线操作不常用，这里只给出大致思路和代码。 我们发现长度类似的区间查询时只会用到一个一维数组，用二维数组很浪费空间。比如P1440。所以我们可以对长度进行桶排序（注意不是计数排序，我们只需要对长度的对数排序即可），然后每迭代一次进行一系列查询。代码如下：

//P1440
#include<iostream>
#include<vector>
using namespace std;
int n,f[2000005][2],a[2000005],cpL[2000005],pos[2000050],p2[2000050];
struct qj{
    int x,y,ans;
};
vector<qj>v[25];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    int m;
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    cpL[0]=-1;
    for(int i=1;i<=n;i++){
        f[i][0]=a[i];
        cpL[i]=cpL[i/2]+1;
    }
    for(int i=2;i<=n;i++){
        int x,y;
        y=i-1,x=max(y-m+1,1);
        int m=cpL[y-x+1];
        p2[i]=m;
        pos[i]=v[m].size();
        v[m].push_back({x,y,a[x]});
    } 
    for(int j=1;j<=cpL[n];j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][0]=f[i][1]=min(f[i][0],f[i+(1<<(j-1))][0]);
        } 
        for(int i=0;i<v[j].size();i++){
            int x=v[j][i].x,y=v[j][i].y;
            int m=cpL[y-x+1];
            v[j][i].ans=min(f[x][1],f[y-(1<<m)+1][1]);
        }
    }
    cout<<0<<endl;
    for(int i=2;i<=n;i++){
        printf("%d\n",v[p2[i]][pos[i]].ans);
    }
    return 0;
}