imicola ST表
ST表

ST表

312 字 · 约 1 分钟

ST表,又称稀疏表,通过采取预处理的方案储存不同长度的区间答案,从而在查询时候非常高效

ST表一般用于解决区间最值,可重复贡献的问题

使用ST表需要注意以下问题:

  • 静态区间查询
  • 运算必须满足 结合律 和 幂等律
  • 常见问题有:
    • 区间最大最小值
    • 区间GCD
    • 区间按位与,按位或

这里给一份参考代码

struct ST
{
    int maxn;
    vector<i64> logtab;
    vector<vector<i64>> st;
    ST(int maxk)
    {
        maxn = maxk;
    }
    void pre(const vector<i64> &a)
    {
        // 预处理log表
        logtab.resize(maxn + 1);
        int K = __lg(maxn) + 1;
        st = vector<vector<i64>>(maxn, vector<i64>(K));
        logtab[1] = 0;
        for (i64 i = 2; i <= maxn; i++) {
            logtab[i] = logtab[i / 2] + 1;
        }
        // 预处理st表
        // 初始化
        for (i64 i = 0; i < maxn; i++) {
            st[i][0] = a[i];
        }
        // pre
        for (i64 j = 1; (1 << j) <= maxn; j++) {
            for (i64 i = 0; i + (1 << j) <= maxn; i++) {
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    i64 get(int l, int r)
    {
        i64 k = logtab[r - l + 1];
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};
cpp