ST表(Sparse Table稀疏表)

主要用于解决RMQ(区间最值问题)

问题描述: 给定N个数字, M次查询, 每次查询给定去间[L, R], 求区间内的最大值.
N <= 1e5, M <= 1e5

暴力肯定是不行了, 大家估计都会线段树, 线段树可以区间查询, 也可以区间更新, 功能很多, 但是建树O(N), 查询是O(logN).
随着M增大, O(logN)的查询不够优秀了, 我们需要O(1)查询!!!
于是乎, 我们不需要区间更新等操作而只需要区间查询的时候, 我们选择ST表.

ST表的核心是:

f(i,j)=max(f(i,j−1),f(i+2^(j−1),j−1);

f(i, j)代表的是从i开始(包括i)的共2^j个数字长度的区间的最大/小值.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5;

int a[maxN + 10];
int lg[maxN + 10];
int maxn[maxN + 10][50];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        lg[i] = lg[i / 2] + 1;
    }
    for (int i = 1; i <= n; i++) {
        maxn[i][0] = a[i];
    }
    for (int i = 1; i <= lg[n]; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            maxn[j][i] = max(maxn[j][i - 1], maxn[j + (1 << n)][i - 1]);
        }
    }
    int l, r;
    while (m--) {
        scanf("%d %d", &l, &r);
        int len = lg[r - l + 1];
        printf("%d\n", max(maxn[l][len], maxn[r - (1 << len) + 1][len]));
    }
    return 0;
}

啊这,