RMQ 算法详解（区间最值问题）

问题介绍

RMQ问题是OI中经常遇到的问题，主要是一下形式：

• 给你一堆数，不断的对里面的数进行操作，例如：让某个数加几、让某个数乘几，中途查询区间内的最大值或是最小值。

解决方法

暴力法

• 优点
  容易想出此方法，代码简单，容易理解。
• 缺点
  时间复杂度高，效率低，在处理大数据是会超时。

ST表法

ST表（Sparse Table）是一种用于高效解决静态RMQ问题的数据结构，通过倍增思想和动态规划实现O(1)时间复杂度的区间查询。

• 优点
  快速，时间复杂度低，效率高。
• 缺点
  相对较长

基本思想

• 预处理：构建二维DP数组st[i][j]，存储区间[i, i+2^j-1]的最值

• 查询：将任意区间[L,R]拆分为两个重叠的$2^k$长度区间，取最值

算法步骤

• 预处理阶段

初始化：st[i][0] = a[i]（单个元素的最值）

递推公式：st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1])

时间复杂度：$O(NlogN)$

• 查询阶段

计算区间长度指数：k = log2(R-L+1)

查询公式：max(st[L][k], st[R-(1<<k)+1][k])

时间复杂度：$O(1)$

C++实现

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;const int MAXN = 1e5+5, LOG = 20;
int st[MAXN][LOG], Log2[MAXN];void init(int n, vector<int>& arr) {// 预处理对数表Log2[1] = 0;for(int i=2; i<=n; i++) Log2[i] = Log2[i/2] + 1;// 初始化ST表for(int i=0; i<n; i++)st[i][0] = arr[i];// 动态规划构建ST表for(int j=1; j<LOG; j++) {for(int i=0; i+(1<<j)<=n; i++) {st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);}}
}int query(int L, int R) {int k = Log2[R-L+1];return max(st[L][k], st[R-(1<<k)+1][k]);
}int main() {vector<int> arr = {3, 2, 4, 5, 1, 6, 0, 8};int n = arr.size();init(n, arr);cout << "区间[1,4]最大值: " << query(1,4) << endl; // 输出5cout << "区间[0,7]最大值: " << query(0,7) << endl; // 输出8return 0;
}