知识点
一 . 基本概念
ST表:又名稀疏表,用来处理区间最值查询的离线算法,用到了倍增的思想
某个区间查询问题是否适用ST表,关键在于其进行的操作是否允许区间重叠。
例如max(a,b,c) = max{max(a,b),max(b,c)}就可以用ST表维护,而区间和问题则不能维护。
在时间复杂度上:预处理时间O(nlogn),单词查询O(1),时间复杂度:O(nlogn+m) 。
二 . 实现方式
设二维数组f[i][j]代表从i号位置开始往后推个单位长度的区间里的最大值,即区间的最大值
① 预处理
这里要注意更新顺序,因为其中 j (第二维)才是阶段,而第一维 x 是状态,所以对于 j 的循环要放在最外层。
② 查询
当查询任意区间的最大值时,先计算出指数k,满足不等式,将该不等式同时转换为以为底的数:,可得:k为当前小于区间长度且能满足2的k次幂的值最大的数。
文章来源地址https://www.toymoban.com/news/detail-515058.html
左端点:num[l][l+2^k-1]
右端点:num[r-2^k+1][r]
注意这里的的表示方法:(1<<k)=pow(2,k)=
!!位运算优先级很低但是运算速度快,需要加括号
模板题
例题: 洛谷 P3865 【模板】ST 表 / 洛谷 P1816 忠诚
题目背景
这是一道 ST 表经典题——静态区间最大值(静态RMQ问题)
题目描述
给定一个长度为 N 的数列,和 M 次询问,求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数 N,M,分别表示数列的长度和询问的个数。
第二行包含 N 个整数(记为 ),依次表示数列的第 i 项。
接下来 M 行,每行包含两个整数 ,表示查询的区间为 。
输出格式
输出包含 M 行,每行一个整数,依次表示每一次询问的结果。
输入输出样例
输入 #1
8 8 9 3 1 7 5 6 0 8 1 6 1 5 2 7 2 6 1 8 4 8 3 7 1 8
输出 #1
9 9 7 7 9 8 7 9
说明/提示
对于 30% 的数据,满足 。
对于 70% 的数据,满足 。
对于 100% 的数据,满足 ,,,。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define re register
using namespace std;
const int maxn=1e5+5;
int f[maxn][21];
int n,m;
inline int read() //快读模板
{
re int x=0,f=1;
re char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline int rmq(int l,int r)
{
re int k=log2(r-l+1);
//如果2k+1<=r-l+1
//while (1<<(k+1)<=r-l+1) ++k; 同样的效果
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;++i)
{
f[i][0]=read();
}
for(re int j=1;j<=21;++j)
{
for(re int i=1;i+(1<<j)-1<=n;++i)
{
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
for(re int i=1;i<=m;++i)
{
re int g=read(),b=read();
printf("%d\n",rmq(g,b));
}
return 0;
}
相关练习
1 . 洛谷 P1440 求m区间内的最小值
朴素ST表(80pts):会存在两个数据MLE。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
#define re register
using namespace std;
int n,m,t;
const int maxn=2e7+5;
int a[maxn],f[maxn][21];
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
inline void ST() //ST表预处理
{
for(re int i=1;i<=n;++i)
{
f[i][0]=a[i];
}
for(re int j=1;j<=20;++j)
{
for(re int i=1;i+(1<<j)-1<=n;++i)
{
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
inline int query(int l,int r) //ST表查询
{
int k=log2(r-l+1);
return min(f[l][k],f[r-(1<<k)+1][k]); //要注意这里r-(1<<k)+1的写法,不要写漏东西
}
int main()
{
n=read(); m=read();
for(re int i=1;i<=n;++i)
{
a[i]=read();
}
ST();
for(re int i=1;i<=n;++i)
{
re int l=i-m,r=i-1;
if(r<1) //第一个数据输出为0
{
printf("0\n");
continue;
}
if (l<1) l=1;
//如果查询的范围大到超出i之前的所有数,从边界1开始处理
printf("%d\n",query(l,r));
}
return 0;
}
(待填坑)滚动数组优化
我不会。。。
2 . 洛谷 P2251 质量检测
该题注意查询部分:第 i 行的数表示 Q[i + M - 1] 即可。文章来源:https://www.toymoban.com/news/detail-515058.html
到了这里,关于【数据结构:线性表】倍增表(ST表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!