专栏文章

RMQ(Range Minimun,Maximum Query)

LLQ_Q
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqicm6y
此快照首次捕获于
2025/12/04 05:17
3 个月前
此快照最后确认于
2025/12/04 05:17
3 个月前
查看原文

例题展示

P3865 【模板】ST 表 && RMQ 问题

题目大意

给定n个数，有m个询问，对于每个询问，你需要回答区间 [l,r] 中的最大值
数据范围：1≤N≤10^5 1≤M≤2*10^6

思路

暴搜

在每次查询时，遍历一遍
(O(n^2)) n,m≤5000
显然超时

ST表

简介

ST表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。
注：可重复贡献问题 是指对于运算opt，满足xoptx=x，则对应的区间询问就是一个可重复贡献问题。例如，最大值有max(x,x)=x，gcd 有 gcd(x,x)=x，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外opt还必须满足结合律才能使用 ST 表求解。

基本思想

ST 表基于倍增思想，可以做到 O(nlog₂n) 预处理，O(1) 回答每个询问。
注意：不支持修改操作。

具体思路

我们发现 max(x,x)=x，也就是说，区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。
如果手动模拟一下，可以发现我们能使用至多两个预处理过的区间来覆盖询问区间，也就是说询问时的时间复杂度可以被降至 O(1)，在处理有大量询问的题目时十分有效。

实现

STEP1
定义 m[i][j] 表示以 i 为起点长度为 2^j 的间的最大值
显然对于 m[i][0] ,最大值为 a[i] 。
STEP2
对 m 进行初始化
显而易见定义任意一个长度为 2^i 的区间，这个区间的最大值可以通过比较两个长度为 2^(i-1) 的区间得来
令其中一个长度为 2^(i-1) 的区间中的所有元素组成的集合为 A ,另一个同样长度的区间的所有元素组成的集合为 B，长度为 2^i 的区间所以元素组成的集合为C 即 A∩B为空 A∪B=C
代码实现：
CPP
	int L=log2(n)+1;
	for(int i=1;i<=L;i++)
		for(int j=1;j<=n;j++)
			if(j+(1<<i)-1<=n) m[j][i]=max(m[j][i-1],m[j+(1<<(i-1))][i-1]);
STEP3
对于每个询问 [l,r]
显而易见，我们把它分成两部分：[l,l+2^s-1] 与 [r-2^s+1,r] ，其中 s=log₂(r-l+1)。两部分的结果的最大值就是回答
代码实现：
CPP
max(m[l][logn[cnt]],m[r-(1<<logn[cnt])+1][logn[cnt]])

最终代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+2,MAXI=18;
int n,t,a[MAXN],m[MAXN][MAXI],logn[MAXN]={-1};
//m[i][j]表示从 i~i+2^j-1 区间的最大值 
int main(){
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]); 
		m[i][0]=a[i];
	}
	int L=log2(n)+1;
	for(int i=1;i<=L;i++)
		for(int j=1;j<=n;j++)
			if(j+(1<<i)-1<=n) m[j][i]=max(m[j][i-1],m[j+(1<<(i-1))][i-1]);
	//对区间进行预处理 
	for(int i=1;i<=n;i++) logn[i]=logn[i/2]+1;  
	//对log2进行预处理，使查询时复杂度为O(1) 
	while(t--){
		int l,r;
		scanf("%d%d",&l,&r);
		int cnt=r-l+1;
		printf("%d\n",max(m[l][logn[cnt]],m[r-(1<<logn[cnt])+1][logn[cnt]]));
	} 
	return 0;
}

课后习题

Q1: P2880 [USACO07JAN] Balanced Lineup G
Q2: P1198 [JSOI2008] 最大数
————变式Q2讲解————
Q3: P2471 [SCOI2007] 降雨量

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...