【倍增】RMQ问题与ST表

Allen-yang2010 / 2024-10-13 / 原文

问题叙述

RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大/最小值。

显而易见的，可以用线段树写。但是~~我这样的蒟蒻早就忘了线段树怎么写了~~，而且由于该问题不涉及修改操作，所以线段树十分没有性价比。
这是就需要用到好理解又好写的ST表了。

算法思路

ST表是用于解决可重复贡献问题的数据结构。

倍增思想：我们考虑将 $st_{i,j}$ 定义为起点为 $i$, 到 $i + 2^j - 1$ 位置的所有元素的最大值。例如 $st_{i,1}$ 表示 $i$ 和 $i + 1$ 中的最大值。

该如何处理转移过程？

把当前区间拆成两个大小相等的区间，用动态规划求出答案。
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
这样就可以保证该区间内所有的元素都被转移了。预处理就是将 $st_{i,0}$ 表示第 $i$ 个元素的最大值，即本身。

查询过程？

查询过程也一样，分成两个区间，这里我用的是 st[i][k] 和 st[r - (1 << k) + 1][k]，因为这样刚好有一部分重叠，可以保证答案转移的正确性，然后分别求最大值最后在汇总一下。 return max(st[l][k], st[r - (1 << k) + 1][k]);其中的k = log[r - l + 1]，用于分隔两个区间。至于怎么求 $\log$，这里我用的是传统求 lg[i] + 1` 的写法，见下方代码。

总代码

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

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 5;
ll st[MAXN][25], lg[MAXN];

ll Query(ll l, ll r){
	ll k = lg[r - l + 1] - 1;
	return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	ll n, m;
	cin >> n >> m;
	for(ll i = 1; i <= n; i ++){
		cin >> st[i][0];
	}
	for(ll i = 1; i <= n; i ++){
		lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
	}
	for(ll j = 1; j <= 20; j ++){
		for(ll i = 1; i + (1 << j) - 1 <= n; i ++){
			st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
	while(m --){
		ll l, r;
		cin >> l >> r;
		cout << Query(l, r) << "\n";
	}
	return 0;
}