稀疏表

區間求某個東西在程式競賽中是一種很常見的需求，例如「求一個序列之中，區間的總和」就是一種常見又簡單的問題，當我們要快速計算一個區間的總和時，我們會使用前綴和（見基礎演算法 / 前綴和與差分），只要把前綴到 $r$ 的總和，扣掉前綴到 $\ell-1$ 的總和，就會得到 $\ell+1$ 到 $r$ 之間的總和了，又直覺又好寫。然而，我們換一種操作，像是取 $\min$，就沒有那麼簡單了！

我們可以那麼輕易的算出區間和，是因為「加法」是一個可逆的操作，只要把加換成減，就可以把多餘的部分給去掉，但是取 $\min$ 是一個不可逆的操作，要是不小心跟一個超級小的數字取 $\min$，就再也無法推回本來的數字了……不過，取 $\min$ 有一個加法沒有的好處：重複取 $\min$ 不會有任何影響！不像是求總和的時候，一個數字被算到兩次那就是算錯了。

那麼，這會帶給我們什麼優勢呢？若是我們知道兩個區間 $[\ell_1, r_1)$、$[\ell_2, r_2)$ 的區間最小值，這兩個區間聯集起來剛好是 $[\ell, r)$，那麼無論這兩個區間是否重疊，我們都只需要求它們最小值中比較小的那個，就是 $[\ell, r)$ 的最小值了。至於這兩個區間要是誰呢？因為我們需要能輕易知道它們之中的最小值，不外乎就是我們要先預處理好，因此我們需要預處理的區間數量不能太多，而且任何一個區間都要有辦法表示成兩個預處理區間的聯集──像是，我們預處理好所有長度是二的冪次的區間的最小值，這樣一來，因為一個長度是 $x$ 的區間，一定是兩個長度是 $2^{\lfloor \log_2 x \rfloor}$ 的聯集，而這種區間又只有 $O(N \log N)$ 個，完美符合我們的需求。

具體來說，假設我們預先計算好了，$s[k][i]$ 是 $[i, i+2^k)$ 的區間最小值，那麼一個區間 $[l, r)$ 的最小值就是
$$
\min( s[k][l], s[k][r-2^k] ), \quad k = \lfloor \log_2 (r-l) \rfloor
$$

下一個問題就是如何計算 $s[k][i]$ 了，這也很簡單，長度是 $2^k$ 的區間就是兩個長度是 $2^{k-1}$ 的區間拼起來嘛，所以
$$
s[k][i] = \min(s[k - 1][i], s[k - 1][i + 2^{k-1}])
$$
也就是把 $[i, i+2^{k-1})$ 和 $[i+2^{k-1}, i+2^{k})$ 拼起來成 $[i, i+2^{k})$，其實根本就只是倍增法而已。

這個資料結構就叫作 sparse table，中文會叫它稀疏表，只要是「重複計算沒有關係」的運算，都可以用 sparse table 來做。這樣一來，我們就能在 $O(N \log N)$ 的預處理時間之後，花費 $O(1)$ 的時間就能回答一筆區間最小值的詢問了。空間複雜度是 $O(N \log N)$，在記憶體限制比較小的題目可能會需要注意一下。

#include <bits/stdc++.h>
using namespace std;

struct SparseTable {
    int n;
    vector<vector<int>> s;
    SparseTable(const vector<int> &a): n(a.size()), s(__lg(n) + 1, vector<int>(n)) {
        s[0] = a;
        for (int i = 1; i <= __lg(n); i++)
            for (int j = 0; j + (1 << i) <= n; j++)
                s[i][j] = min(s[i - 1][j], s[i - 1][j + (1 << (i - 1))]);
    }
    int query(int l, int r) {
        int k = __lg(r - l);
        return min(s[k][l], s[k][r - (1 << k)]);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    SparseTable table(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << table.query(l, r) << "\n";
    }

}