RMQ问题中的ST算法

Nebulary / 2023-08-08 / 原文

RMQ问题中的ST算法

长为 n 的数组 a ，m次询问，求l~r中最大值是多少

// RMQ问题中的ST算法
// m次询问，求l~r中最大值是多少
#include<bits/stdc++.h>
#define reg register
using namespace std;

// 读取输入的函数
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}

// 输出结果的函数
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}

const int MAXN=100005;
vector<int > a; // 存储输入数据的数组
int n,f[MAXN][21],m; // f[i][j]表示区间[i, j]的最大值

// ST预处理函数
void ST_prework(){
	for(reg int i=1;i<=n;i++) f[i][0]=a[i]; // 将第一个元素作为区间的最大值
	int t=log(n)/log(2)+1; // 确定二维数组f的维度
	for(reg int j=1;j<t;j++){ // 从第二个维度开始遍历二维数组f
		for(reg int i=1;i<=n-(1<<j)+1;i++){ // 从第一个维度开始遍历一维数组f的第一部分
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); // 根据状态转移方程更新f[i][j]的值
		}
	}
	return ;
}

// ST查询函数，返回区间[l, r]的最大值
int ST_query(int l, int r){
	int g=log(r-l+1)/log(2); // 计算区间长度的对数，向上取整得到二进制位数g
	return max(f[l][g],f[r-(1<<g)+1][g]); // 根据状态转移方程和边界条件返回区间最大值
}

// 主函数，读取输入数据，调用ST预处理函数和查询函数，输出结果
int main(){
	n=read(),m=read(); // 读取输入数据的数量n和查询次数m
	a.push_back(0); // 在a数组末尾添加一个元素，用于记录空元素的位置，方便后续处理边界情况
	for(reg int i=1;i<=n;i++)a.push_back(read()); // 按照顺序读取输入数据并存储到a数组中
	ST_prework(); // 对输入数据进行预处理，构建ST表f
	for(reg int i=1;i<=m;i++){ // 对于每次查询，调用ST查询函数并输出结果
		int p=read(),q=read(); // 读取查询的起始位置p和结束位置q
		write(ST_query(p, q)); // 将查询结果写入输出流中，并换行分隔每个查询结果
		putchar('\n'); // 在每次查询后换行，使得输出更加清晰易读
	}
	return 0;
}