ST表

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

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

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

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

基本思路

ST表的基本思路是 倍增法

假设我们有一个长度为$n$的数组a[0…n-1],我们预处理一个二维数组 st[i][j]
st[i][j]表示从 $i$ 开始,长度为 $2^j$ 的区间答案

预处理

• 初始化 st[i][0] = a[i]
• 状态转移:
  $st[i][j]=f(s[i][j-1],st[i+2^{j-1}][j-1])$
  即将长度为 $2^j$的区间拆成两个长度$2^{j-1}$的区间

查询

• 对于区间[L,R]:
  • 令 k = floor(log_2(R-L+1))
  • 有 ans = f(st[L][k],st[R-(1 << k)+1][k]
  • 对于log我们可以预处理log表
• 下图展示了ST表倍增的过程
  

这里给一份参考代码

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]);
    }
};