淺談RMQ算法

• • 前言
  • RMQ是什麼
  • RMQ算法描述
  • RMQ算法的不足
  • RMQ算法例題

前言

這篇文章，是一篇總結RMQ算法的一篇文章，若有疑問或建議，請于下方留言，謝謝！

RMQ是什麼？

RMQ（Range Minimum/Maximum Query），即區間最值查詢。

是指這樣一個問題：對于長度為n的數列A，回答若幹詢問RMQ（A,i,j）(i,j<=n)，傳回數列A中下标在i，j之間的最小/大值。

這兩個問題是在實際應用中經常遇到的問題，而RMQ算法是解決這兩種問題的比較高效的算法。

當然，該問題也可以用線段樹解決，算法複雜度為：O(N)~O(logN)，而線段樹代碼遠遠比我們今天讨論的RMQ要長要難了解的多，這裡我們暫不介紹。

我們遇到這種區間最值查詢問題的時候，通常會想到兩種想法

每次查詢時暴力掃描區間，時間複雜度單次查詢O(n),n次查詢便是O(n^2),超過1e4基本上就TLE了

開一個二維數組（空間複雜度O（n*n））,預處理答案在數組中，預處理複雜度O(n^2)，單次查詢O(1)。

顯然這些算法都是渣渣，慢的要死，那麼有什麼搞基進階的方法來解決這一類問題呢？

答案是倍增思想。（大概是這樣的）

RMQ算法描述

我們以最大值來诠釋RMQ算法

1. 令A[i]存儲我們要求的數列，F[i][j]表示從第i個位置開始，往後的2^j-1個數字中，最大的數字是多少。
2. 預處理F數組，對j從大到小枚舉。每次處理F[i][j]的時候，F[i][0~j-1]都已經處理好了，那麼F[i][j]=max(F[i][j-1],F[i+2^(j-1)][j-1])，因為j最大到log2n，是以預處理的操作的時間複雜度為O(nlog2(n))。
3. 有了F數組啦，現在我們查詢的話就很簡單了。比如說我們查詢區間(i,j)，那麼我們令k =⌊log2(i)+j-1⌋,那麼我們查詢的結果就是max(F[i][j],F[j-(2^k)+1][k])，可以明顯看到時間複雜度為O（1）的，而且保證能夠覆寫到整個區間。

代碼描述如下

預處理操作

void init_rmq(int m) {
    for(int i=;i<=m;i++) 
        f[i][]=a[i];
    for(int j=;(<<j)<m;j++) {
        for(int i=;i<=m;i++) {
            if(i+(<<j)- <= m) {
                f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);
            }
        }
    }
}
           

查詢操作

int query_rmq(int l,int r) {
    int i=;
    for(;(<<i)+l-<=r;i++){};
    i--;
    return min(f[l][i],f[r-(<<i)+][i]);
}
           

RMQ算法的不足

我們發現RMQ算法複雜度竟然如此低，能夠在O(log2(n))的時間内預處理，O(1)的複雜度單點查詢，經常用于優化常數（卡常數是個神奇的東西），看來是一個好東西，但是但是

它不支援修改，隻能維護最大最小值，不能維護區間和等會影響答案的東西（此時還是打那騷長的線段樹吧）

RMQ算法例題

這裡給出習題練練手吧

洛谷P1816 忠誠 （傳送門）

題目描述

老管家是一個聰明能幹的人。他為财主工作了整整10年，财主為了讓自已賬目更加清楚。要求管家每天記k次賬，由于管家聰明能幹，因而管家總是讓财主十分滿意。但是由于一些人的挑撥，财主還是對管家産生了懷疑。于是他決定用一種特别的方法來判斷管家的忠誠，他把每次的賬目按1，2，3…編号，然後不定時的問管家問題，問題是這樣的：在a到b号賬中最少的一筆是多少？為了讓管家沒時間作假他總是一次問多個問題。

輸入輸出格式

輸入格式：

輸入中第一行有兩個數m,n表示有m(m<=100000)筆賬,n表示有n個問題，n<=100000。

第二行為m個數,分别是賬目的錢數

後面n行分别是n個問題,每行有2個數字說明開始結束的賬目編号。

輸出格式：

輸出檔案中為每個問題的答案。具體檢視樣例。

輸入輸出樣例

輸入樣例#1：

10 3

1 2 3 4 5 6 7 8 9 10

2 7

3 9

1 10

輸出樣例#1：

2 3 1

解決方案

這題目實在是不能再不能裸的RMQ裸題了，如果沒有完全掌握的RMQ的話還是可以練練手的，或者可以掌握思想後來實作一番，頗有成就感，比線段樹好看多了。。。

代碼

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int size =+;
int a[size];
int f[size][];

void init_rmq(int m) {
    for(int i=;i<=m;i++) 
        f[i][]=a[i];
    for(int j=;(<<j)<m;j++) {
        for(int i=;i<=m;i++) {
            if(i+(<<j)- <= m) {
                f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);
            }
        }
    }
}

int query_rmq(int l,int r) {
    int i=;
    for(;(<<i)+l-<=r;i++){};
    i--;
    return min(f[l][i],f[r-(<<i)+][i]);
}

int main() {
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=;i<=m;i++) 
        scanf("%d",&a[i]);
    init_rmq(m);
    for(int i=,l,r;i<=n;i++) {
        scanf("%d%d",&l,&r);
        printf("%d ",query_rmq(l,r));
    }
    return ;
}