Sparse Table ST表笔记

问题叙述

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

显而易见的，可以用线段树实现。但是由于该问题不涉及修改操作，且线段树太长了不好写，十分浪费时间。

这是就需要用到好理解又好写的ST表了。

算法思路

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

倍增思想：我们考虑将 定义为 起点为 , 到 位置的所有元素的最大值。例如 表示 和 中的最大值。

转移过程

把当前区间拆成两个大小相等的区间，用动态规划求出答案。

$$st_{i,j} = max(st_{i,j - 1},st_{i + 2^{j-1},j - 1})$$

这样就可以保证该区间内所有的元素都被转移了。预处理就是将 表示第 个元素的最大值，即本身。

查询过程

查询过程也一样，分成两个区间，这里我用的是 和 ，因为这样刚好有一部分重叠，可以保证答案转移的正确性，然后分别求最大值最后在汇总一下。

$$max(st_{l,k}, st_{r - 2^k + 1,k})$$

其中的 k = log[r - l + 1]，用于分隔两个区间。至于怎么求 ，这里我用的是传统求 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;
}

更多思考

为什么 ST表 似乎很少被用于区间求和之类的问题？

这个问题看起来很傻，却很有用。大概有如下两个原因：

• 可以用前缀和，更好写还不容易错
• ST表如果想要O(1)查询，需要满足所求的问题区间能够重复覆盖。因为查询是两边重叠算的啊

显然，对于第二点，区间求和并不满足条件（如果重复覆盖就会有许多值被加了多次）。那么可不可以进行二进制拆分呢？答案显然是可以的。