ST算法
🥍

ST算法

Tags
RMQ
ST算法
Last Updated
Last updated May 14, 2022
Author
Created
Oct 21, 2020 08:28 AM
Featured
Featured
Slug

简介

ST整个算法就是基于倍增的产物,用于解决 RMQ(区间最值)类问题。它可以在的时间预处理后,用的时间复杂度查找一个区间内的最大值。(如果你想在询问的时候再进行修改,那么还是推荐你使用线段树)。

开始了……

首先,我们知道,任意一个正整数都能标示为的形式,因此,我们定义为从开始个数中的最大值。那么,不难想到,就是中的最大值。到这里,可能会让人想到动态规划或递推,那么我们就需要一个转移公式。
初始化数组的整体思想与区间DP有些相似,先附上代码,再解释。
int t=log(n)/log(2)+1; //换底公式 for (int j = 1; j < t; ++j) //预处理 for(int i=1;i<=n-(1<<j)+1;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//相当于是状态转移方程
第一重循环像是区间DP中的状态(不懂没关系),是中的。第二轮循环枚举起点的最大值为。由对数的换底公式得,
所以
注意:库中函数为底的。
int t=log(n)/log(2)+1;
 
有了的最大值也很好解释了。在循环里,每次将从上一个状态中转移。
因为,因此将二分,从两个区间中选取最大值。即
下面问题来了,怎么查询呢?
查询时可以将所表示的区间二分,我们可以找到至少一个数使,因此可以将分成 (其中),即中最大值为
到这里,基本就解决了,还有几条优化建议:
  1. 读入优化(当然输出优化也可以)
  1. 为保证查询复杂度为,用数组保存结果。
  1. 可以省略数组,直接输入到

例题

某谷有一模板题,名曰“ST表”,在这里:
附上代码供参考:
 
// // Created by admin on 2020/7/11. // #include <bits/stdc++.h> using namespace std; int n,f[105000][40],m; double lo[105000]; inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int main() { int x,y; n=read();m=read(); for(int i=1;i<=n;i++) { f[i][0]=read(); lo[i]=log(i); } int t=lo[n]/lo[2]+1; //换底公式 for (int j = 1; j < t; ++j) //预处理 for(int i=1;i<=n-(1<<j)+1;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//相当于是状态转移方程 while(m--) { x=read();y=read(); int k=lo[y-x+1]/lo[2]; printf("%d\n",max(f[x][k],f[y-(1<<k)+1][k])); } return 0; }
 
备注:此题数组定义请严格按照题目中数据范围,不然会满天飞。
 
 
 



参考资料:
  1. 李煜东 《算法竞赛进阶指南》