【模板】 ST表 log的预处理

【模板】 ST表 log的预处理

ST表是用于解决可重复贡献问题 的数据结构。

ST表基于倍增思想，可以做到(O(nlogn))预处理，(O(1))回答询问。但是不支持修改操作。

举例来说，区间最大值就是一个可重复贡献问题，即使处理的区间有重叠，也不影响答案

令(f[i][j]) 表示区间([i,i+2^j-1]) 的最大值。

显然(f[i][0] = a_i)

根据定义可以推出转移方程

[f[i][j] = max(f[i][j - 1],f[i + 2^{j-1}][j-1]]) ]

对于每个询问([l,r]) ,可以分成两个部分(f[l,l+2^s-1],f[r-2^s+1,r]) ，取最大值即可，正确性就在于上述的可重复贡献

为了不重复调用(log)函数，不妨预处理(log)函数

[logn[1] = 0 \ log[i] = log[i/2]+1 ]

类似地，ST表还可以处理类似的问题

如“区间按位和”，“区间按位或”，“区间GCD”等

代码

int f[maxn][21];
int logn[maxn];

void pre() {
    logn[1] = 0;
    logn[2] = 1;
    for (int i = 3; i < maxn; i++)
        logn[i] = logn[i >> 1] + 1;
}

int main() {
    int n = readint(), m = readint();
    for (int i = 1; i <= n; i++) f[i][0] = readint();
    pre();
    for (int j = 1; j <= 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    for (int i = 1; i <= m; i++) {
        int x = readint(), y = readint();
        int s = logn[y - x + 1];
        printf("%d
", max(f[x][s], f[y - (1 << s) + 1][s]));
    }
}