RMQ算法

RMQ

RMQ(range min/max query)区间最值查询算法。经典场景：给定一个数组A[1...N]，有N个数字。查询区间[l,r]，求该区间的最大/最小值。常规方法是对[l,r]进行遍历，复杂度O(n)。当查询次数K巨大时，性能会很差。RMQ算法需要nlogn时间进行预处理，之后以O(1)时间响应查询。(当然还可以使用线段树)

原理

使用二维数组dp,dp[i][j]表示从第i位开始连续2^j个数中的最值。例如dp[2][1]就是第二个数开始连续两个数的最值(A[2],A[3]),dp[i][0]表示第i个数本身。
求解dp[i][j]时，我们知道共2^j个数，必定是2的次幂，根据二进制数的性质，这2^j个数可以通过2^(j-1)做界定分成i ~ i+2^(j-1)-1和i+2^(j-1) ~ i+2^(j)-1长度相等的两部分。
那么转移方程就可以表示为：
dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])

void rmq_init(vector<int>& arr)
{
    int  N = arr.size();
    for(int i=1;i<=N;i++)
        dp[i][0]=arr[i];//初始化
    for(int j=1;(1<<j)<=N;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
// j控制迈的步子，分别求得每2个、每4个、每8个数..的最值。
// i j 不可互换，否则变成了求第一个数开始时的2个数、4个数、8个数的最值。

分析

RMQ的查询部分，假定需要查询[l,r]的最小值，令k = log2(r-l+1),则区间[l,r]的最小值 = min(dp[l][k],dp[r-(1<<k)+1][k])
dp[l][k]维护的是区间[l,l+2^k-1],dp[r-(1<<k)+1][k]维护的是区间[r-2^k+1,r]。
只需要保证r-2^k+1<=l+2^k-1就可以保证RMQ算法的准确性。
理由：
若假设 r-2^k+1<=l+2^k-1这个式子成立，
即r-l+2<=2* 2^(k)
又k=log2(r-l+1),故r-l+2<=2*(r-l+1)
得r-l>=0
当r>=l时，可令k=log2(r-l+1)使RMQ算法成立。
查询部分的代码：

int rmq(int l,int r)
{
    int k=log2(r-l+1);
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}

例子

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>dp(100,vector<int>(100));
void rmq_init(vector<int>& arr)
{
    int  N = arr.size();
    for(int i=1;i<=N;i++)
        dp[i][0]=arr[i];//初始化
    // nlogn的预处理
    for(int j=1;(1<<j)<=N;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int l,int r)
{
    int k=log2(r-l+1);
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{
    // 数组长度10，有效部分从下标1开始
    vector<int>v = {0,1,2,4,3,5,6,9,12,34,7};
    for(int i=1;i<=10;++i) cout<<v[i]<<" ";
    cout<<endl;
    rmq_init(v);
    while(1)
    {
        int a,b;
        cin>>a>>b;
        cout<<rmq(a,b)<<endl;
    }
    return 0;
}