4.1 KiB
【数据结构】ST表-RMQ问题
RMQ(Range Maximum(Minimum) Query)问题，查询区间最大值或最小值，相比线段树，为静态查询，复杂度O(nlogn)
作用
查询区间 最大值 或 最小值
复杂度
O(nlogn)预处理O(1)查询
算法：倍增思想
以最大值为例，最小值取min同理
ST算法
1、预处理
状态表示
设a[i]是要求区间最值的数列，f[i][j]表示 从第i个数起连续2^j个数中的最大值
举栗子：
a数列为：\large 3 2 4 5 6 8 1 2 9 7
f[1][0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。
f[1][1] = max(3,2) = 3
f[1][2]=max(3,2,4,5) = 5
f[1,3] = max(3,2,4,5,6,8,1,2) = 8;
初始值
可以容易的看出f[i,0]就等于a[i]。（dp的初始值）
状态转移
\large f[i,j] = max(f[i,j-1],f[i+2^{j-1},j-1])
这样的话可以在nlogn的时间下完成f数组的建立，下边是区间最大值的查询，对于区间[l,r]，存在一个k使得r-l+1>=2^k且r-l+1<2^{k+1},这样的话区间[l,r]的最大值就是max(f[l,k],f[r-2^k+1,k]),查询可以在常数级完成。
Q:为什么j是外循环而i是内循环?
能不能 调换一下嘞？
答案是 不可以 。
你可以这样来理解：动态规划体现在二维数组形式上，就是一个二维填表的过程，可能采用的顺序是：
- 从左到右，从上到下去填写
- 从上到下，从左到右去填写
- 从右下角向左上角去填写
- ....
具体该怎么填写，其实是和实际场景相关的，必须保证无后效性，就是这块填写完了就是填写完了，不能一会用到时说还没有填写，那就彼此依赖不上了。本题如果按列填写，就是j依赖于j-1,也就是按列，可以完成任务。如果是按行，你会发现i是东一下，西一下，跳来跳去，整不好就在下一个要用到前序数字时，它还没有完成填充，这样彼此就无法实现依赖了！因此需要先枚举j，再枚举i。
查询
如何确定k呢？
对于每个查询 [l,r]，需要先找出最大的一个满足 \large 2^k<len 的 \large k，其中
len=r−l+1，方法就是两边求对数：
\large log_2{2^k}<log_2(len) \\
\Rightarrow \\
k<log_2(len)
k要想取最大的整数，就是(int)(log_2(len))
如果是给整数赋值，就不用写强制转换，故直接写成：
int k = log2(len);
构造交集
查询时通过构建2^k的方法，造成\large [a,a+2^k-1]与\large [b-2^k+1,b]存在一个交集，分别求f(a,k)与f(b-2^k+1,k)，然后取一个max就是答案，虽然这里有一部分是重复的，但求最大值不怕重复！同时，也因为这个原因，使得st算法，也就只能用来计算最大最小值，不能用来处理其它需求。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 18;
int n, m;
int w[N];
int f[N][M];
void rmq() {
for (int j = 0; j < M; j++) // 注意是j在外层
for (int i = 1; i + (1 << j) - 1 <= n; i++) // i在内层
if (j == 0) // base case 边界值
f[i][j] = w[i];
else
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r) {
int len = r - l + 1;
int k = log2(len);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
rmq(); // ST表初始化
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
printf("%d\n", query(l, r));
}
return 0;
}