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

#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;
}