C++如何实现一个稀疏表(Sparse Table)_C++解决RMQ(区间最值查询)问题的O(1)算法

稀疏表通过倍增思想预处理静态数组，实现O(1)区间最值查询。预处理STi表示从i开始长度为2^j的区间最值，递推式为STi=min(STi, STi+(1

稀疏表（Sparse Table）是一种用于快速查询静态数组区间最值（RMQ，Range Minimum/Maximum Query）的数据结构。它通过预处理实现 O(1) 的查询时间复杂度，适用于不修改原数组的场景。预处理时间复杂度为 O(n log n)，空间复杂度也为 O(n log n)。

稀疏表的基本思想

稀疏表的核心是倍增思想：对于每个位置 i，预先计算从 i 开始长度为 2^j 的区间的最值。这样任意一个区间 [l, r] 都可以被两个长度为 2^k 的区间覆盖，其中 k = floor(log2(r - l + 1))，这两个区间有重叠也没关系，只要能完全覆盖 [l, r] 即可。

查询时取这两个区间的最值的较小（或较大）值即可，因此可在常数时间内完成。

实现步骤

为了快速得到每个长度对应的 k = floor(log2(len))，我们可以预处理一个 log 数组，避免每次调用 log 函数。

立即学习“C++免费学习笔记（深入）”；

2. 构建稀疏表 ST

设 ST[i][j] 表示从位置 i 开始，长度为 2^j 的区间中的最小值（或最大值）。递推公式为：

ST[i][0] = arr[i] （长度为 1）

ST[i][j] = min(ST[i][j-1], ST[i + (1

Ideogram

Ideogram是一个全新的文本转图像AI绘画生成平台，擅长于生成带有文本的图像，如LOGO上的字母、数字等。

下载

3. 查询 [l, r] 区间最小值

计算 k = log2(r - l + 1)

结果为 min(ST[l][k], ST[r - (1

C++ 实现代码

以下是一个完整的 C++ 实现，支持区间最小值查询：

#include 
#include 
#include 
using namespace std;

class SparseTable {
private:
    vector> st;  // 稀疏表
    vector log;         // 预处理 log2 数组
    int n;

public:
    // 构造函数，输入数组构建稀疏表
    SparseTable(vector& arr) {
        n = arr.size();
        log.resize(n + 1);
        // 预处理 log2 值
        for (int i = 2; i <= n; i++) {
            log[i] = log[i / 2] + 1;
        }

        int k = log[n] + 1;  // 最大可能的 j
        st.assign(n, vector(k));

        // 初始化长度为 1 的区间
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }

        // 倍增构建稀疏表
        for (int j = 1; j < k; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }

    // 查询 [l, r] 区间最小值，闭区间
    int query(int l, int r) {
        int len = r - l + 1;
        int k = log[len];
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

使用示例

假设我们有一个数组，想多次查询其子区间的最小值：

#include 
using namespace std;

int main() {
    vector arr = {1, 3, 2, 5, 4, 7, 0, 6};
    SparseTable st(arr);

    cout << st.query(1, 4) << endl;  // 输出 2 (min of [3,2,5,4])
    cout << st.query(0, 7) << endl;  // 输出 0
    cout << st.query(3, 5) << endl;  // 输出 4

    return 0;
}

如果需要支持最大值查询，只需将 min 改为 max 即可。

基本上就这些。稀疏表适合静态数据下的高频 RMQ 查询，实现简单且效率极高。注意它不能处理更新操作，如需支持更新，应考虑线段树或树状数组。