ST 表 SPARSE TABLE

· · 科技·工程

前言

第一服役期都要结束了还写什么博客

ST 表是一种基于预处理、倍增、分块的数据结构，主要解决 RMQ 问题，并且就离线询问来讲（它也只能离线询问）是相当高效的，当然预处理的可能要稍微花点与其他数据结构同级别的时间，不太支持修改，与最值强联系的性质才能用。

正文

0x01.ST 表基础

理论基础

有一种东西，叫做二的次幂，还有一种东西，叫做对数，对于很大的数量，比如说 10^9，取一个以 2 为底的对数（取整）就可以得到极小的 31，降了 7 个数量级。

还有最值，有一种性质是

x=\max(\{A\},\{B\},\{C\})\Rightarrow x=\max(\{A\}\cup\{C\},\{B\}\cup\{C\} ) x=\min(\{A\},\{B\},\{C\})\Rightarrow x=\min(\{A\}\cup\{C\},\{B\}\cup\{C\} )

也就是对于一段整数序列的区间 [l,r] 内，有 \forall\lceil\frac{r-l+1}{2}\rceil\leq z\leq r-l+1,z\in Z 满足 \max[l,r]=\max(\max[l,l+z-1],\max[r-z+1,r])。

那么对于一段长度为 n 序列 \{a_i\} ，我们可以对于每个位置记录 \log_2n 个 st_{i,j} 表示区间 [i,i+2^j-1] 内的 \max a_i 或者 \min a_i，于是对于任意的离线询问 [l,r] 的最值，答案就是

\max(st_{l,t},st_{r-2^t+1,t}) \text{or}\min(st_{l,t},st_{r-2^t+1,t})(t=\lfloor\log_2(r-l+1)\rfloor)

具体的，就可以在 n\log n 的时间复杂度内预处理，然后 O(1) 离线查询区间最值哩。

代码实现

假设给定一个序列，离线求区间最大值。

首先，为了避免 \log_2 x 带来的较大常数，我们一般预处理出 \log_2x,1\leq x\leq n，时间复杂度 O(n)。
然后为了得到 st_{i,j}，因为 st_{i,j}=\max(st_{i,j-1},st_{i+2^j,j-1})，所以按照区间以二的次幂增大的方式更新每个位置的 st_{i,j}，有一个 O(n) 的对 st_{i,0} 的预处理，然后时间复杂度 O(n\log n)。
最后，在询问时，先处理出区间长度对应的 \log 整数，然后借助理论基础里的式子就可以 O(1) 得到想要的答案。

\max[l,r]=\max(st_{l,t},st_{r-2^t+1,t}) \text{or}\min(st_{l,t},st_{r-2^t+1,t})(t=\lfloor\log_2(r-l+1)\rfloor)

以下是样例代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,m;
int a[N];

int st[N][12];
int logn[N];

void init(){
    logn[1]=0;
    for(int i=2;i<=n;i++)   logn[i]=logn[i/2]+1;//取对数

    for(int j=1;j<=logn[n];j++)//枚举区间长度
        for(int i=1;i+(1<<j)-1<=n;i++)//枚举位置，更新st数组
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

int ask(int l,int r){//O(1)查询
    if(l>r) return 0;
    int t=logn[r-l+1];
    return max(st[l][t],st[r-(1<<t)+1][t]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),st[i][0]=a[i];//输入+预处理
    init();
    for(int i=1,l,r;i<=m;i++){
        scanf("%d%d",&l,&r);
        printf("%d\n",ask(l,r));
    }
    return 0;
}

贝斯特的优化：有一种东西，叫做地址访问优化，也就是对于数组来讲，维数小的放前面，会比维数大的放前面访问更快，这种东西对于极大的数组来讲，优化相当之大，在状态压缩等应用中也有十足的表现。

贝蒂的练习