POJ 3264：RMQ 問題與稀疏表算法詳解

問題背景

給定一個長度為 m 的數組，需回答 n 次查詢：區間 [u, v] 中最大值與最小值的差。數據範圍較大，暴力查詢會超時，需用 O(1) 查詢、O(m log m) 預處理的稀疏表算法。

稀疏表核心思想

稀疏表是一種靜態區間查詢數據結構，利用倍增思想預計算長度為 2^k 的區間最值。查詢時將任意長度區間分解為兩個重疊的 2^k 長度區間，取其最值即可。

預處理過程

• b[i] 存儲 floor(log2(i))，用於快速確定查詢長度對應的 k 值。
• fl[i][j] 存儲從 i 開始長度為 2^j 區間的最小值。
• fr[i][j] 存儲對應的最大值。
• 狀態轉移：fl[i][j] = min(fl[i][j-1], fl[i + 2^(j-1)][j-1])，fr 同理。

查詢操作

對於區間 [l, r]，長度 len = r - l + 1，k = b[len]。
最小值 = min(fl[l][k], fl[r - 2^k + 1][k])
最大值 = max(fr[l][k], fr[r - 2^k + 1][k])

完整代碼實現

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 200010
using namespace std;
int a[maxn], m, n, b[maxn], fl[maxn][50], fr[maxn][50];

void solve() {
    b[1] = 0;
    for (int i = 2; i <= m; i++) {
        b[i] = b[i - 1];
        if ((1 << (b[i] + 1)) == i) b[i]++;
    }
    for (int i = 0; i < m; i++) fl[i][0] = fr[i][0] = a[i];
    for (int i = m - 1; i >= 0; i--)
        for (int j = 1; i + (1 << j) - 1 < m; j++) {
            fl[i][j] = min(fl[i][j - 1], fl[i + (1 << (j - 1))][j - 1]);
            fr[i][j] = max(fr[i][j - 1], fr[i + (1 << (j - 1))][j - 1]);
        }
}

int qma(int l, int r) {
    int len = r - l + 1;
    int k = b[len];
    return max(fr[l][k], fr[r - (1 << k) + 1][k]);
}

int qmi(int l, int r) {
    int len = r - l + 1;
    int k = b[len];
    return min(fl[l][k], fl[r - (1 << k) + 1][k]);
}

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) cin >> a[i];
    solve();
    while (n--) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        printf("%d\n", qma(u, v) - qmi(u, v));
    }
    return 0;
}

關鍵細節與易錯點

1. b 數組的計算：利用位運算判斷 2 的冪次，避免浮點運算誤差。
2. 預處理循環順序：i 從大到小，j 從小到大，保證依賴的子問題已計算。
3. 查詢時兩個區間有重疊，但不影響最值結果。
4. 數組下標從 0 開始，輸入的 u, v 需遞減 1。

複雜度總結

• 預處理時間：O(m log m)
• 單次查詢：O(1)
• 空間複雜度：O(m log m)

稀疏表適用於靜態數組的冪等操作最值查詢，是 RMQ 經典解法之一。