ST算法（Sparse Table，稀疏表）

大家好，欢迎来到IT知识分享网。

定义

ST表（Sparse Table）是一种用于高效处理区间查询的数据结构。它可以在O(1)的时间复杂度内回答某一区间的最值查询（最小值、最大值等）。ST表使用动态规划的思想，通过预处理的方式来快速计算出各个区间的最值。

概念引入

ST 表基于倍增思想，可以做到 $O(nlogn)$预处理，$O(1)$ 回答每个询问。但是不支持修改操作
基于倍增思想，我们考虑如何求出区间最大值。按照一般的倍增流程，每次跳 $2^i$ 步
我们发现 $max(x,x)=x$，也就是说，区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间包含所求的区间，最终计算出的答案就是正确的

应用范围

• RMQ（英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值）
• 区间按位与(或)
• 区间 GCD

【模板】ST 表 && RMQ 问题

来源

洛谷ST表模板题

思路

考虑朴素算法，每次都遍历区间$[l,r]$，那么它的时间复杂度高达$O(nm)$必然会超时
这时我们就需要用到$O(nlogn)$的算法，即ST倍增

我们先开一个st数组，行代表当前位置，列代表长度,它存入的值为最大值
首先我们要明白一个知识点：任何一个数都可以用二进制的数来表示
例如一个区间为30，那么它可以被分为1 2 4 8 15(不够16剩下的数拎出来)
那么这个区间可操作的次数为4次（1 2 4 8），那么我们可以用$lo{g}_2$函数求出一个区间可进行的操作次数

接着我们将小区间进行倍增，假设我们一开始的区间为1，初始化$st[1][0]=a[1]$
（解释：当前位置为1，长度为$2^0=1$,那么这个区间的最大值就为它本身，即$a[1]$）

从该位置进行倍增，每次倍增长度为$2^j$,那么这个区间就被划分为两个$2^{j-1}$
我们拿$j=3$举例

对于每次询问，我们先算出$[l-r]$在二进制下的长度
$那么左区间从l开始，长度为2^{len},右区间为r-2^{len}+1，长度也为2^{len}$
（右区间保证长度为len，所以需要+1）

接下来看代码

code

const int N=1e5+5; int a[N],lg[N]; int st[N][31];//i代表当前位置，j代表2^j（长度） int n,m; void init(){ 
    lg[1]=0; for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;//log2初始化 for(int i=1;i<=n;++i) st[i][0]=a[i];//当长度为2^0=1时，最大值为本身 for(int j=1;j<=lg[n];++j)//以二进制优化来划分区间 for(int i=1;i<=n-(1<<j)+1;++i){ 
   //长度为2^j st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); //划分两个区间，左区间从i开始，长度为2^j-1,右区间从i+2^j-1，长度也为2^j-1 } } void solve(){ 
    cin >> n >> m; for(int i=1;i<=n;++i) cin >> a[i]; init(); while(m--){ 
    int l,r; cin >> l >> r; int len=lg[r-l+1];//区间l-r在二进制下的长度 cout << max(st[l][len],st[r-(1<<len)+1][len]) << endl; //左区间从l开始，长度为2^len,右区间为r-2^len +1，长度也为2^len } return ; } 

区间gcd

来源

洛谷gcd区间

思路

套RMQ模板，将max函数改为gcd函数即可
相当于每次都是求区间的最大公因数

code

const int N=1e3+5; int a[N],lg[N]; int st[N][31]; int n,m; int gcd(int a,int b){ 
    return b?gcd(b,a%b) : a; } void init(){ 
    lg[1]=0; for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;++i) st[i][0]=a[i]; for(int j=1;j<=lg[n];++j) for(int i=1;i<=n-(1<<j)+1;++i){ 
    st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } void solve(){ 
    cin >> n >> m; for(int i=1;i<=n;++i) cin >> a[i]; init(); while(m--){ 
    int l,r; cin >> l >> r; int len=lg[r-l+1]; cout << gcd(st[l][len],st[r-(1<<len)+1][len]) << endl; } return ; } 

st表的应用题

来源

P7167 [eJOI2020 Day1] Fountain

思路

考点：栈+st表

如果水超出盘子的容量，会溢出到往下一个直径比所在盘子要大的盘子里面
“后面第一个比自己大的元素”，这不就是单调栈的用法吗

因此我们可以开2个二维数组 $nxt,sum$ ,nxt数组用于存下标，sum数组用于存容量
(为什么开2个二维数组呢？方便我们接下来进行倍增操作)
若当前下标的直径比栈首元素的直径大，那么当前$nxt[s.top()]$存的是当前下标i，sum存的是当前下标的容量，即
$nxt[s.top()][0]=i，sum[s.top()][0]=c[i]$
和上面模板题一样，列存的是长度，那么该点在长度 $2^0=1$，它的下一个元素为当前下标 $i$
存完之后将栈首出队，最后若栈还剩余，那么这些元素的下一个元素必然是水池，将这些元素都标记为0，即
$nxt[s.top()][0]=0$

接下来看代码

code

const int N=1e5+5; int d[N],c[N]; int nxt[N][30],sum[N][30]; int n,q; void init(){ 
    stack<int> s; for(int i=1;i<=n;++i){ 
    while(!s.empty() && d[i]>d[s.top()]){ 
    nxt[s.top()][0]=i; sum[s.top()][0]=c[i]; s.pop(); } s.push(i); } while(!s.empty()){ 
    nxt[s.top()][0]=0; s.pop(); } for(int j=1;(1<<j)<=n;++j) for(int i=1;i<=n-(1<<j);++i){ 
    nxt[i][j]=nxt[nxt[i][j-1]][j-1]; sum[i][j]=sum[i][j-1]+sum[nxt[i][j-1]][j-1]; } } void solve(){ 
    cin >> n >> q; for(int i=1;i<=n;++i){ 
    cin >> d[i] >> c[i]; } init(); while(q--){ 
    int r,v; cin >> r >> v; if(c[r]>=v){ 
    cout << r << endl; continue; } v-=c[r]; for(int i=17;i>=0;--i){ 
    if(nxt[r][i] && v>sum[r][i]){ 
    v-=sum[r][i]; r=nxt[r][i]; } } cout << nxt[r][0] << endl; } return ; }