|
|
|
|
|
## [【数据结构】$ST$表-$RMQ$问题](https://www.lyroch.site/posts/e62206d1/)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
$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])$$
|
|
|
|
|
|
|
|
|
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2022/07/04/64630_bc14d198fb-1.jpg'></center>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这样的话可以在$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))$
|
|
|
|
|
|
如果是给整数赋值，就不用写强制转换，故直接写成：
|
|
|
|
|
|
```c++
|
|
|
|
|
|
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$算法，也就只能用来计算最大最小值，不能用来处理其它需求。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
https://www.acwing.com/problem/content/description/1275/
|
