## [【数据结构】$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/