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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-11-25

浏览次数：次

返回列表

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

c++如何实现一个稀疏表(sparse table)_c++解决rmq(区间最值查询)问题的o(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] 即可。

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

实现步骤

1. 预处理对数表（可选但推荐）

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

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

N世界

一分钟搭建会展元宇宙

138 查看详情 N世界

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

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

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

C++ 实现代码

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

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

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

public:
    // 构造函数，输入数组构建稀疏表
    SparseTable(vector<int>& 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<int>(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 <iostream>
using namespace std;

int main() {
    vector<int> 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 查询，实现简单且效率极高。注意它不能处理更新操作，如需支持更新，应考虑线段树或树状数组。

以上就是C++如何实现一个稀疏表(Sparse Table)_C++解决RMQ(区间最值查询)问题的O(1)算法的详细内容，更多请关注其它相关文章！

# 是一个 # 云南网站建设在哪里 # seo发包开发合作 # 采摘园营销推广 # 营销策划网络建设和推广 # 济南推广好的网站 # 宁波网站建设详细方案 # 潢川网站建设多少钱 # 音乐营销推广平台哪个好 # 公司适合做哪些网站推广 # 双辽seo优化 # c++ # 解决方法 # 尼克 # 重写 # 这两个 # 如何实现 # 有什么 # 数据结构 # 最小值 # 长度为