RMQ问题（区间最值查询）

RMQ（区间最值查询）是指这样一个问题：给定一个数组，其中有N个数字，给定区间[l ，r]，询问在这个区间内的最值。

这种的解决方法：暴力，线段树（效率较低）

所以我们给出一种效率较高的算法：st算法，该算法能在O（nlogn）的预处理后达到O（1）的查询效率。

核心思路：

1.预处理（dp）：

假设数组arr为：1，2，6，8，4，3，7

我们设二维数组dp[i][j]表示从第i位开始连续 $2^j$ 个数中的最小值。例如dp[2][1]就表示从第二位数开始连续两个数的最小值（也就是从第二位数到第三位数的最小值），即2，6中的最小值，所以dp[2][1] = 2;

其实我们求 dp[i][j] 的时候可以把它均分成两部分，第一部分是从 $i$ 到 $i+2^(^j^-^1^)-1$ ，第二部分从 $i+2^(^j^-^1^)$ 到 $i+2^j-1$ ，为什么可以这么分呢？其实我们都知道二进制数前一个数是后一个的两倍，那么可以把 $i$ 到 $i+2^j-1$ 这个区间通过 $2^(^j^-^1^)$ 分成相等的两部分，那么转移方程很容易就写出来了。（dp[i][0]就表示第i个数字本身）

dp[i][j] = min(dp [i][j - 1], dp [i + (1 << j - 1)][j - 1])

代码实现：

 1 void rmq_init(int arr[], int N) { //dp是全局数组，N指一共N个数
 2     for(int i = 1; i <= N; i++) {
 3         dp[i][0] = arr[i]; 
 4     }
 5     for(int j = 1; (1<<j) <= N; j++) { //注意ij顺序
 6         for(int i = 1; i+(1<<j)-1 <= N; i++) {
 7             dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); //先更新每两个元素中的最小值，然后通过每两个元素的最小值获得每4个元素中的最小值，依次类推更新所有长度的最小值。
 8         }
 9     }
10 }

2.查询部分：

1 int rmq(int l, int r) {
2     int k = log2(r-l+1); //c语言math.h头文件
3     return min(dp[l][k], dp[r-(1<<k)+1][k]);
4 }

只写一个dp[][]只能查询2的n次方个数，若要查询的数的个数不是2的指数个则无法精准查询（比如查询5个数），故用

dp[l][k], dp[r-(1<<k)+1][k]以包含整个查询区间。

参考博客：https://blog.csdn.net/qq_41311604/article/details/79900893