banner
cos

cos

愿热情永存,愿热爱不灭,愿生活无憾
github
tg_channel
bilibili

RMQ問題- ST表算法

ST 表是什麼#

ST 表是一個用來解決區間最值問題查詢的算法
它用O (nlogn) 複雜度預處理,可以實現 O (1) 複雜度的查詢。
缺點:無法支持在線修改
模板題:ST 表 - 洛谷

1. 預處理#

用一個二維數組 dp [i][j] 表示下標為 i ~ i + 2^j^ - 1 的最值(最大 or 最小值)

①易知邊界條件 dp [i][0] 為 a [i],既 i~i 的最大值為其本身
②接下來是狀態轉移方程,如圖

1 << j 相當於 2^j^#

image
初始化代碼

void init(int n) {
    for (int i = 0; i < n; i++) {
        dp[i][0] = a[i];
    }
    for (int j = 1; (1<<j) <= n; j++) {
        for (int i = 0; i + (1<<j) <= n; i++) {
            dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}

2. 查詢#

接下來就是查詢,因為每次給出的查詢區間長度不一定恰好為 2^j,所以我們需要以下定理:(參考大佬證明

2^log(a)^>a/2#

log (a) 表示小於等於 a 的 2 的最大幾次方#

eg(4)=2,log(5)=2,log(6)=2,log(7)=2,log(8)=3,log(9)=3……

若我們要查詢 a~b 區間的最小值
首先我們求出區間長度len = b-a+1 並令 t = log(len)
由上述定理,2^t^>len/2
也就是說,2^t 在 a,b 區間的右半邊
a,b 的最小值,即為 min(a ~ (a+2^t^-1), (b-2^t^+1) ~ t)如圖
在這裡插入圖片描述
查詢代碼:

ll sol(int a, int b) {
    int t = (int) (log(b-a+1.0)/log(2.0));
    return max(dp[a][t], dp[b-(1<<t)+1][t]);
}

3. 完整代碼#

題目:ST 表 - 洛谷
開了 O2 優化和快讀才能 ac

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100000;
typedef long long ll;
ll a[maxn];
ll dp[maxn][25];//此處以最大值為例
void init(int n) {
    for (int i = 0; i < n; i++) {
        dp[i][0] = a[i];
    }
    for (int j = 1; (1<<j) <= n; j++) {
        for (int i = 0; i + (1<<j) <= n; i++) {
            dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}
ll sol(int a, int b) {
    int t = (int) (log(b-a+1.0)/log(2.0));
    return max(dp[a][t], dp[b-(1<<t)+1][t]);
}
int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    init(n);
    while(m--) {
        int x,y;
        cin >> x >> y;
        cout << sol(x-1,y-1) << endl;
    }
    return 0;
}
読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。