RMQ問題--ST算法(Sparse Table)

RMQ(Range Minimum/Maximum Query)問題是求區間最值問題。

這裡介紹的ST算法，雖然預處理的複雜度大了點O(nlogn)，但是查詢複雜度可以降低到O(1)。

首先，預處理的時候，是一個動态規劃的過程。假設，給出一個數列1, 3, 7, 2, 4, 9, 0，用數組a[]來存儲，下标從1開始，便于處理。mx[i, j]表示的是從下标i開始的長度為1<<j的區間最大值，例如，mx[2, 2]就是閉區間[2, 5](3, 7, 2, 4)的最大值，即為7。mi[i, j]同理。我們很容易發現，mx[1, 0] = 1, mx[2, 0] = 3....即mx[i, 0] = a[i]。于是，我們就可以得到狀态以及初始值了。接下來，求狀态轉移方程，當i加上j的一半，不超過數列長度時，我們就可以mx[i, j] = max(mx[i][1<<(j-1)], mx[i+1<<(j-1)+1][1<<(j-1)])，這裡有點二分的思想。

然後，就是求最值了。以最大值為例，這裡我們仍舊用到了二分的思想。将區間二分一下，然後，傳回兩者最大值。區間會出現交叉，但是并不影響解題。

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

const int maxn = 1000;
int n, q;
int a[maxn], mx[maxn][maxn], mi[maxn][maxn];

void stinit() {
    for(int i = 1; i <= n; i++) mx[i][0] = mi[i][0] = a[i];
    int p = (int)(log(n*1.0)/log(2.0));
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= n; j++) {
            mx[j][i] = mx[j][i-1];
            mi[j][i] = mi[j][i-1];
            if(j+(1<<(i-1)) <= n) {
                mx[j][i] = max(mx[j][i], mx[j+(1<<(i-1))][i-1]);
                mi[j][i] = min(mi[j][i], mi[j+(1<<(i-1))][i-1]);
            }
        }
}

int stmin(int l, int r) {
    int p = (int)(log((r-l+1)*1.0)/log(2.0));       
    return min(mi[l][p], mi[r-(1<<p)+1][p]);    //由于求p向下取整，導緻l+p可能達不到r，但是l+p至少能區間[l, r]的一半
}

int stmax(int l, int r) {
    int p = (int)(log((r-l+1)*1.0)/log(2.0));
    return max(mx[l][p], mx[r-(1<<p)+1][p]);
}

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    stinit();
    while(q--) {
        int l, r;
        cin >> l >> r;
        printf("maxmum number is : %d, minimum number is %d\n", stmax(l, r), stmin(l, r));
    }
    return 0;
}
           

如果問題求的是最值的下标，那麼也很簡單，隻要把二維數組存的值改為下标即可。

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


const int maxn = 1000;
int n, q;
int a[maxn], mx[maxn][maxn], mi[maxn][maxn];


void stinit() {
    for(int i = 1; i <= n; i++) mx[i][0] = mi[i][0] = i;
    int p = (int)(log(n*1.0)/log(2.0));
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= n; j++) {
            mx[j][i] = mx[j][i-1];
            mi[j][i] = mi[j][i-1];
            if(j+(1<<(i-1)) <= n) {
                if(a[mx[j+(1<<(i-1))][i-1]] > a[mx[j][i]])
                    mx[j][i] = mx[j+(1<<(i-1))][i-1];
                if(a[mi[j+(1<<(i-1))][i-1]] < a[mi[j][i]])
                    mi[j][i] = mi[j+(1<<(i-1))][i-1];
            }
        }
}


int stmin(int l, int r) {
    int p = (int)(log((r-l+1)*1.0)/log(2.0));
    if(a[mi[l][p]] < a[mi[r-(1<<p)+1][p]]) return mi[l][p];
    else return mi[r-(1<<p)+1][p];
}


int stmax(int l, int r) {
    int p = (int)(log((r-l+1)*1.0)/log(2.0));
    if(a[mi[l][p]] > a[mi[r-(1<<p)+1][p]]) return mx[l][p];
    else return mx[r-(1<<p)+1][p];
}


int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    stinit();
    while(q--) {
        int l, r;
        cin >> l >> r;
        printf("maxmum number's location is : %d, minimum number's location is %d\n", stmax(l, r), stmin(l, r));
    }
    return 0;
}