洛谷题解P3865 【模板】ST表 暨 浅谈ST表

原题传送门

( ext{Solution})

这是一道ST表经典题——静态区间最大值

本文以此题为例，来浅析 ( ext{ST}) 表

(1).概述
( ext{ST}) 表是一个解决 ( ext{RMQ}) 问题的很有力的工具
它的本质其实是动态规划，运用到的思想主要是倍增思想。
可以做到 (O(nlogn)) 预处理，(O(1)) 查询。

(2).解析
((1)).预处理
与 ( ext{DP}) 相似，这里我们令 (st[i][j]) 表示从 (i) 开始 (2^j) 个数的最值
易得 (st[i][0] = a[i]) （即输入时可以直接输入 (st[i][0])）
状态的转移 : (以最大值为例，最小值同理)

[st[i][j] = max(st[i][j-1],st[i+(1 < <(j-1))][j-1]) ]

这里，我们应用的是 (2^j = 2^{j-1}+2^{j-1}) 这个关键的转化条件。
即可以把从 (i) 开始遍历 (2^j) 个位置转化为先遍历 (2^{j-1}) 个位置，再从当前位置再次遍历 (2^{j-1}) 个位置
状态转移方程即来源于此，不过需注意，第二次遍历的起点非 (i)，是 (i+2^{j-1})

所以可以得到以下代码 :

for(int j=1;j<=21;j++){		//2^21 = 2097152 > 2*10^5
	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]);
	}
}

((2)).查询
首先，对于一个区间 ([l,r]) ，我们要知道它的长度是 (r-l+1) 并非 (r-l) （计算时当前元素也被包含在内，所以应该 (+1)）
其次，对于一个在这个区间 ([l,r]) 内的位置 (i)，(st[i][j]) 中的 (j)，它最多遍历 (log_2 r-l+1) 个位置，所以可以先预处理出来，再从左端点和右端点分别开始查询，保证 (O(1)) 且每个元素都被查询到。
所以可以得到以下代码 :

for(int i=1;i<=m;i++){
	read(l);read(r);
	len=log2(r-l+1);	//预处理 
	printf("%d
",max(st[l][len],st[r-(1<<len)+1][len]));	//注意+1 
}

( ext{Code})

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
inline void read(int &x){
	int f=1;
	char ch=getchar();
	x=0;
	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();
	}
	x*=f;
} 
int n,m;
int st[100010][21];
int l,r;
inline int max(int x,int y){return x>y?x:y;}
int main(){
	read(n);read(m);
	for(int i=1;i<=n;i++) read(st[i][0]);
	for(int j=1;j<=21;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	} 
	int len;
	for(int i=1;i<=m;i++){
		read(l);read(r);
		len=log2(r-l+1);
		printf("%d
",max(st[l][len],st[r-(1<<len)+1][len]));
	}
	return 0;
}