ST表(静态区间最大值/最小值)

题目

理论

  • 用于静态查询区间最大值/最小值，时间复杂度O(nlogn), 查询O(1)
  • f[i][j]:从i开始，长度是2^j的区间中最大值，即区间[i, i + (1 << j) - 1]
  • 状态转移：分为前半段和后半段求值f[i][j] = max/min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1])
  • 查询：分为左段和右段max/min(f[l][k], f[r - (1 << k) + 1][k]);(k = log2(区间长度)下取整)

模板

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cmath>

using namespace std;
const int N = 200010, M = 18;
//f[i][j]:从i开始，长度是2^j的区间中最大值
int n, m, f[N][M], lo2[N], a[N];

void init()
{
    //预处理log2(下取整)
    for (int i = 0; i < M; i ++ ) lo2[1 << i] = i;
    int mx = 0;
    for (int i = 0; i < N; i ++ )
    {
        mx = max(mx, lo2[i]);
        lo2[i] = mx;
    }
    //st表
    for (int j = 0; j < M; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (!j) f[i][j] = a[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r)
{
    int len = r - l + 1;
    int k = lo2[len];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    init();
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }
    
    return 0;
}