To boldly go where no one has gone before.

【学习笔记】ST表

2019-09-25 13:54:00


ST 表是一种$O(nlogn)$预处理,查询速度达到$O(1)$的数据结构。上次遇一道题正解本来是$O(nlogn)$的树上倍增,而卡掉$O(nlog^2n)$的树剖 + 线段树。由于只是查询区间最大值,所以可以直接把线段树换成 ST 表,然后就可以凭空优化掉一个$log$,达到比倍增更优的速度。

一种对数计算方式

    int k = (int) (log(n) / log(2));

虽然会损失精度,但是在取整的时候这点精度也不值一提了。

如果害怕 gg,还可以使用以前用过的递推式,使用时要注意 $log(n) = log2[n]-1$(递推时就已经$+1$,所以要减回去)

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n, m, a;
int st[MAXN][40];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a);
        st[i][0] = a;
    }
    int k = (int) (log(n) / log(2));
    for(int j = 1; j <= k; j++)
        for(int i = 1; i <= n - (1 << j) + 1; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
///         注意 i, j 枚举顺序,以及 i 的范围
    int l, r;
    while(m--) {
        scanf("%d %d", &l, &r);
        int p = (int) (log(r - l + 1) / log(2));
        printf("%d\n", max(st[l][p], st[r - (1 << p) + 1][p]));
    }
    return 0;
}