ST表维护区间最值

（图片来源：ST表（保姆级，简单易懂）-CSDN博客）

ST表可以用上面这张图来理解。

要求长度为2^N的区间最值，就是在求左右两个2^N-1区间最值中较大的那个。

依次类推，预处理所有2倍数长度区间最值的复杂度将为O(logN*N)。

要求[L，R]区间的最大值，等效于分别求 [L, L+2^K - 1] 和 [R - 2^K + 1, R]这两个区间的最值。

每次查询的复杂度为O(1)。

模板题：P3865 【模板】ST 表 && RMQ 问题 - 洛谷

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int n, m;
int lg[maxn],st[maxn][30];

void init(){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		cin>>st[i][0];
	}
	// lg[1] = 0;
	for(int i = 2 ; i <= n ; i ++){
		lg[i] = lg[i/2] + 1;
		// cout<<"log2^"<<i<<" == "<<lg[i]<<"\n";
	}
	for(int i = 1 ; i <= lg[n] ; i ++){
		for(int j = 1 ; j + (1<<i) - 1 <= n ; j ++){
			st[j][i] = max(st[j][i-1], st[j+(1<<(i-1))][i-1]);
		}
	}
}

void solve(){
	int l, r; cin>>l>>r;
	int k = lg[r - l + 1];
	cout<<max(st[l][k], st[r-(1<<k)+1][k])<<"\n";
}

int main(void){
	cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
	init();
	while(m--){
		solve(); 
	}
}

经典例题：P3865 【模板】ST 表 && RMQ 问题 - 洛谷

要求一个[L,R]区间内的极差，就是查询该区间的最大值 - 最小值，可使用ST表解决。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10;

int n, q;
int lg[maxn], st_min[maxn][30], st_max[maxn][30];

void init(){
	cin>>n>>q;
	for(int i = 2 ; i <= n ; i ++){
		lg[i] = lg[i/2] + 1;
	}
	for(int i = 1 ; i <= n ; i ++){
		cin>>st_min[i][0];
		st_max[i][0] = st_min[i][0];
	}
	for(int i = 1 ; i <= lg[n] ; i ++){
		for(int j = 1 ; j + (1<<i) - 1 <= n ; j ++){
			st_max[j][i] = max(st_max[j][i-1], st_max[j + (1<<(i-1))][i-1]);
			st_min[j][i] = min(st_min[j][i-1], st_min[j + (1<<(i-1))][i-1]);
		}
	}
}

void solve(){
	int a, b; cin>>a>>b;
	int k = lg[b-a+1];
	int max_ = max(st_max[a][k], st_max[b-(1<<k)+1][k]);
	int min_ = min(st_min[a][k], st_min[b-(1<<k)+1][k]);
	cout<<max_ - min_<<"\n";
}

int main(void){
	cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
	init();
	while(q--){
		solve();
	}
	return 0;
}