参考博客：https://www.cnblogs.com/wenzhixin/p/9714760.html
预处理时间复杂度是O(nlogn),代码如下：
1 void init(const vector<int>& A) { 2 int n = A.size(); 3 for(int i = 0; i < n; i++) { 4 d[i][0] = A[i];//以i开头，长度为1的最小值是A[i] 5 } 6 7 for(int j = 1; (1 << j) <= n; j++) {//再区间范围内枚举次方 8 for(int i = 0; i + (1 << j) - 1 < n; i++) {//枚举每一个开头，直到没有长度为2的j的区间 9 d[i][j] = min(d[i][j - 1], d[i + (1 << j) - 1][j - 1]); 10 } 11 } 12 }
查询是常数复杂度，这是RMQ的一大优点，相对于线段树的O(logn)复杂度有很大改进。查询的时候先给出最大的k s.t. 2^k<=R-L+1。代码如下：
1 int query(int L, int R) { 2 int k = 0; 3 while((1 << (k + 1)) <= R - L + 1) k++;//若2的k+1次方<= R - L + 1,则k还可以加1 4 return min(d[L][k], d[R - (1 << k) + 1][k]); 5 }
原文：https://www.cnblogs.com/randy-lo/p/12538642.html