ST表详解（附洛谷P3865代码）

a_free_mola_mola

2025-09-30 22:33:36

发布于：四川

9阅读

0回复

0点赞

ST表简介：
ST表所解决的是多询问的RMQ（Range Minimum/Maximum Query，区间最值）问题。

并且，这是一个离线算法，指预处理好答案最后进行输出的算法，不可进行读入时答案的随时更新。

ST表的思想：
ST表对于朴素做法的优化思想来自于DP(实际上就是DP：求出子问题的解，逐个合并得出最终解)。优化的过程类似于快速幂，优化了一个n为log(n)。

ST表通过其状态定义及状态转移实现优化：

普通ST表定义：st[i][j]，代表从i开始的次方个数中的最大/小值。

普通ST表状态转移：st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1])，解析:既然要实现
n到log(n)的时间复杂度优化，那么，这里的取max就应该是把所求区间平均分成两个
部分来求。同时，由于是求max,所以无需担心重叠的问题。

ST表模板代码+要点注释（洛谷P3865）：

#include<iostream>
using namespace std;
int log[100005];
int st[100005][20];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>st[i][0];
	}
	log[0]=-1;
	for(int i=1;i<=n;i++){
		log[i]=log[i>>1]+1;//在枚举j与求取最终答案时需要用log确定边界
	}
	for(int j=1;j<=log[n];j++){
		for(int i=1;i+(1<<j)-1<=n;i++){//减1是因为这是一个闭区间
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		int k=log[r-l+1];//由于询问的区间长度可能不是2的j次方的形式，所以需要k来进行一个拆分
		cout<<max(st[l][k],st[r-(1<<k)+1][k])<<'\n';//把区间按k拆成两段进行求max,这里会有重合来保证st数组第二维中始终是2的j次方的形式
	}
	return 0;
}