【蓝桥杯】RMQ（Range Minimum/Maximum Query）

一.概述

RMQ问题，是求区间最大值或最小值，即范围最值问题。

暴力解法是对每个询问区间循环求解，设区间长度n，询问次数m，则复杂度是O ( nm )。

一般还可以使用线段树求解，复杂度是O(mlogn)。

但还有一种更简便的ST算法，预处理复杂度是O(nlogn)，查询O(1)。

二.ST（Sparse Table）算法

它适用于静态空间的RMQ查询。

给定长度为n的静态数列，做m次询问，每次给定，查询区间[L,R]内的最值。

原理：一个大区间若能被两个小区间覆盖，那么大区间的最值等于两个小区间的最值。（小区间有重合不影响结果）

基本思路：

1）把整个数列划分为很多小区间，并提前计算出每个小区间的最值。

按照倍增分成小区间。

每组小区间的最值，都可以从前一组递推得来。 

设dp[i][j]表示第i处开始的个数字的最值，i是开始位置，j是延伸长度，dp[i][0]是原数组a[i]本身，即边界。

状态转移方程：

这里其实就是把一个区间划分为了两个小区间，通过小区间获得最值。

计算出所有小区间的最值，复杂度为：每一组都需要计算n次，一共有组

时间复杂度为：O(nlogn)

2）对任意一个区间最值查询，找到覆盖它的两个小区间，用两个小区间的最值计算。

以任意元素为起点，有长度为1、2、4、……的小区间，以任意元素为终点，也有长度为1、2、4、……的小区间。

可以将待查询区间[L,R]分为两个小区间，让这两个小区间覆盖[L,R]。一次查询的时间复杂度为：O(1)。

区间长度为len=R-L+1

令,小区间的长度为x。

三.实战演练

//ST算法 区间最大值
#include <iostream>
#include <algorithm>

using namespace std;

const int N=5e5+10;
long long dp[N][20];
int n,q;

long long st(int l,int r){
    int x=0;
    while(l+(1<<(x+1))<=r){
        x++;
    }
    return max(dp[l][x],dp[r-(1<<x)+1][x]);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    //构造dp数组
    for(int i=1;i<=n;i++){
        cin>>dp[i][0];
    }
    
    for(int j=1;j<20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
    
    for(int i=0;i<q;i++){
        int x,y;
        cin>>x>>y;
        cout<<st(x, y)<<'\n';
    }
    return 0;
}