跳转至

ST 表 (Sparse Table)

ST 表（Sparse Table）主要用于求解静态区间最值查询 (RMQ - Range Minimum/Maximum Query) 等满足可重复贡献（幂等性，Idempotence，即 \(x \circ x = x\)）的问题。

预处理时间复杂度为 \(\mathcal{O}(n \log n)\)，单次区间查询只需 \(\mathcal{O}(1)\)。

模版实现 (区间最大值)

0-indexed 简洁实现，预计算 \(\log_2\) 表加速查询。

#include <vector>
#include <algorithm>
#include <cmath>

template <typename T>
struct SparseTable {
    int n;
    int K;
    std::vector<int> lg;
    std::vector<std::vector<T>> st;

    SparseTable(const std::vector<T> &a) {
        n = a.size();
        K = std::__lg(n) + 1;
        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            lg[i] = lg[i >> 1] + 1;
        }

        st.assign(K, std::vector<T>(n));
        st[0] = a;

        for (int j = 1; j < K; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                st[j][i] = std::max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    // 查询区间 [l, r] 的最大值 (0 <= l <= r < n)
    T query(int l, int r) const {
        int k = lg[r - l + 1];
        return std::max(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

扩展：区间 GCD

因为 \(\gcd(x, x) = x\)，GCD 同样满足可重复贡献特性，因此也可以使用 ST 表在 \(\mathcal{O}(1)\) 次 GCD 计算时间内回答区间最大公约数查询。

#include <numeric>

// 只需将递推与查询中的 std::max 替换为 std::gcd 即可:
// st[j][i] = std::gcd(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
// return std::gcd(st[k][l], st[k][r - (1 << k) + 1]);

LeetCode 经典真题精选与题解提示