09-进阶算法/03-ST表

ST表

ST 表（Sparse Table）用于解决可重复贡献问题（如区间最值、区间 GCD），预处理 [math]\displaystyle{ O(n\log n) }[/math]，查询 [math]\displaystyle{ O(1) }[/math]，但不支持修改。

原理

使用倍增思想，[math]\displaystyle{ st[i][j] }[/math] 表示从 [math]\displaystyle{ i }[/math] 开始长度为 [math]\displaystyle{ 2^j }[/math] 的区间的答案。

建表

const int MAXN = 100005;
const int LOGN = 17; // floor(log2(MAXN))
int st[MAXN][LOGN + 1];

void build(int n)
{
    for (int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}

区间查询

// 查询区间 [l, r] 的最大值
int query(int l, int r)
{
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

预计算 log2

int Log2[MAXN];
void pre_log2(int n)
{
    Log2[1] = 0;
    for (int i = 2; i <= n; i++)
        Log2[i] = Log2[i / 2] + 1;
}