引入：

ST表（Sparse Table，稀疏表）是一种用于解决静态区间查询问题的数据结构。

它可以在 O(1) 的时间内完成区间最大值、区间最小值、区间最大公约数等查询。

相比线段树：

  • ST表查询速度更快：O(1)

  • 代码更简单

  • ST表不支持修改操作

因此它适用于：数组不会发生改变，但是需要大量区间查询的情况。

原理：

ST表的核心思想就是：提前计算长度为2的幂次的区间答案，然后利用这些区间组合出任意查询区间。

模板题：P3865 【模板】ST 表 & RMQ 问题 - 洛谷

模板主体：

template<typename T,typename Compare>
class SparseTable {
private:
    vector<T> m_org;
    vector<vector<int>> m_st;
    //比较器对象m_cmp
    Compare m_cmp;
    void init();

public :
    SparseTable(const vector<T>& arr);
    int Query(int l, int r);
};

这里的Compare是一个比较器类型（特殊的结构体），传入greater<int>时表示找出最大值，less<int>表示找出最小值。

1、初始化函数init

template<typename T, typename Compare>
void SparseTable<T, Compare>::init(){
    int n = (int)m_org.size();
    int log2n = (int)log2(n) + 1;
    m_st.assign(log2n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        m_st[0][i] = i;
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << (j - 1)) < n; i++) {
            int idx1 = m_st[j - 1][i];
            int idx2 = m_st[j - 1][i + (1 << (j - 1))];
            m_st[j][i] = m_cmp(m_org[idx1], m_org[idx2]) ? idx1 : idx2;
        }
    }
}

通过二维数组 m_st[j][i] 预处理所有长度为 2^j 的区间最优元素下标，每次把一个大区间拆成两个小区间，然后利用比较器保存更优的那个位置。

2、构造函数

template<typename T, typename Compare>
SparseTable<T, Compare>::SparseTable(const vector<T>& arr){
    int n = (int)arr.size();
    m_org.assign(arr.begin(), arr.end());
    init();
}

复制原数组并调用初始化函数。

3、查询函数

template<typename T, typename Compare>
int SparseTable<T, Compare>::Query(int l, int r){
    if (l == r) {
        return l;
    }
    int k = (int)ceil(log2(r - l + 1)) - 1;
    int idx1 = m_st[k][l];
    int idx2 = m_st[k][r - (1 << k) + 1];
    return m_cmp(m_org[idx1], m_org[idx2]) ? idx1 : idx2;
}

把查询区间 [l,r] 拆成两个长度为 2^k 的重叠区间，然后从 ST 表中直接取出两个区间的最优位置，再比较返回。

完整模板（方便复制）

template<typename T,typename Compare>
class SparseTable {
private:
    vector<T> m_org;
    vector<vector<int>> m_st;
    Compare m_cmp;
    void init();

public :
    SparseTable(const vector<T>& arr);
    int Query(int l, int r);
};

template<typename T, typename Compare>
void SparseTable<T, Compare>::init(){
    int n = (int)m_org.size();
    int log2n = (int)log2(n) + 1;
    m_st.assign(log2n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        m_st[0][i] = i;
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << (j - 1)) < n; i++) {
            int idx1 = m_st[j - 1][i];
            int idx2 = m_st[j - 1][i + (1 << (j - 1))];
            m_st[j][i] = m_cmp(m_org[idx1], m_org[idx2]) ? idx1 : idx2;
        }
    }
}

template<typename T, typename Compare>
SparseTable<T, Compare>::SparseTable(const vector<T>& arr){
    int n = (int)arr.size();
    m_org.assign(arr.begin(), arr.end());
    init();
}

template<typename T, typename Compare>
int SparseTable<T, Compare>::Query(int l, int r){
    if (l == r) {
        return l;
    }
    int k = (int)ceil(log2(r - l + 1)) - 1;
    int idx1 = m_st[k][l];
    int idx2 = m_st[k][r - (1 << k) + 1];
    return m_cmp(m_org[idx1], m_org[idx2]) ? idx1 : idx2;
}