Sparse Table 稀疏表

問題描述

如果只是要求區間總和，可以透過前綴和在 $O(n)$ 預處理後，$O(1)$ 查詢任意區間和。但這種方法無法應用在區間最大值或最小值的查詢上。
那麼，有沒有辦法可以經過預處理後，在 $O(1)$ 內查出任意區間極值呢？

Range Minimum/Maximum Query (RMQ)

這類問題被稱為 RMQ（Range Minimum/Maximum Query），即區間極小值或極大值查詢。

Sparse Table（稀疏表）簡介

操作	時間複雜度
建表（預處理）	$O(n \log n)$
區間查詢	$O(1)$

💡 適用於「靜態」陣列（不會修改），如區間極值查詢問題。

小知識：Sparse Table 是什麼？

Sparse Table 是一種適合靜態陣列的資料結構，可用來在常數時間查詢任意區間的最大或最小值。
它的原理是：將每個起點 $i$ 往後長度為 $2^k$ 的區間極值先計算出來並存表。

例如：

sparse[i][0]：= A[i]
sparse[i][1]：= max(A[i], A[i+1])
sparse[i][2]：= max(A[i], A[i+1], A[i+2], A[i+3])
依此類推…

建表步驟說明

Step 1️⃣：建立 log2 陣列

用來快速查詢 floor(log2(k))，避免重複計算。

for (int i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
}

eg. n = [0,5]

值	log2
0	無意義
1	0
2	1
3	1
4	2
5	2

Step 2️⃣：初始化 sparse[i][0]

每個 sparse[i][0] 就是 A[i] 本身，代表長度為 $2^0 = 1$ 的區間。

for (int i = 0; i < n; i++) {
    sparse[i][0] = A[i];
}

Step 3️⃣：遞推建表

每個 sparse[i][j] 代表從 i 開始、長度為 $2^j$ 的區間極值。由兩個 $2^{j-1}$ 的子區間組成：左：sparse[i][j-1] 右：sparse[i + 2^{j-1}][j-1]

for (int j = 1; j <= lg[n]; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
        sparse[i][j] = max(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
    }
}

查詢任意區間最大值

我們希望查詢的是 2^k 長度的區間，那非常簡單直接查表 sparse[i][k] 即可。

查詢 [L, R] 區間的最大值，流程如下：

計算區間長度：len = R - L + 1
找出最大整數 $k$，使得 $2^k \leq len$：

k = floor(log2(len))

拆成兩段長度為 $2^k$ 的子區間：

第一段：[L, L + 2^k - 1]
第二段：[R - 2^k + 1, R]

最後取兩段的最大值：

💡即使這兩段有重疊也沒關係，因為我們只在意極值，不怕重複計算。

result = max(sparse[L][k], sparse[R - (1 << k) + 1][k]);

eg. [0,8]

len = 8 - 0 + 1 = 9
k = floor(log₂(9)) = 3
左段 [0, 0 + 2^3 - 1] = [0,7]；右段 [8 - 2^3 + 1, 8] = [1,8]
result = max(sparse[0][3], sparse[1][3]);

其餘應用

除了找最大最小值，還可以查 GCD/LCM，把 max() 換成 __gcd() 或 lcm() 而已。

要應用的操作要滿足結合律，因為我們是把不同區間的結果整合！

完整程式碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    // 測資大的話要加
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n;
    vector<int> A(n);
    for (auto& x : A) {
        cin >> x;
    }
    cin >> q;
    vector<int> lg(n + 1);
    lg[1] = 0;
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    vector<vector<int>> sparse(n, vector<int>(lg[n] + 1));
    for (int i = 0; i < n; ++i) sparse[i][0] = A[i];

    for (int j = 1; j < lg[n] + 1; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            sparse[i][j] = max(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        int j = lg[r - l + 1];
        cout << max(sparse[l][j], sparse[r - (1 << j) + 1][j]) << '\n';
    }
}

練習題

d539. 區間 MAX

連結：https://zerojudge.tw/ShowProblem?problemid=d539

這題一定要加 IO 優化！！！
要特別注意 query a b，a 不一定是左邊，所以要先判斷

if(l > r) swap(l,r);

注意是 1-based，用上面的模板必須

l--;
r--;

也不一定要建 log2 陣列，畢竟我們大概只會用到 lg[n] + 1 跟查詢的長度

vector<int> lg(n + 1);
lg[1] = 0;
for (int i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
}
// 可以改成
int max_log = __lg(n) + 1;

int j = lg[r-l+1];
// 可以改成
int j = __lg(r - l + 1);

本題 AC code

0.3s 61.4MB

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n;
    vector<int> A(n);
    for (auto& x : A) {
        cin >> x;
    }
    cin >> q;
    int max_log = __lg(n) + 1;
    vector<vector<int>> sparse(n, vector<int>(max_log));
    for (int i = 0; i < n; ++i) sparse[i][0] = A[i];

    for (int j = 1; j < max_log; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            sparse[i][j] = max(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l > r) {
            swap(l, r);
        }
        l--;
        r--;
        int j = __lg(r - l + 1);
        cout << max(sparse[l][j], sparse[r - (1 << j) + 1][j]) << '\n';
    }
}