DDOSvoid's Blog

st表

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

简介

用来解决RMQ问题，O(nlogn)预处理，O(1)查询

唯一的缺点是只支持静态查询

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
int Log[maxn], st[maxn][21];
void init_st() { Log[0] = -1;
    for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1, st[i][0] = a[i];
    for (int j = 1; j <= 20; ++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]);
}

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

此外还有二维st表，可惜的是只能处理正方形 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline int min(int a, int b, int c, int d) { return min(a, min(b, min(c, d))); } 

int Log[maxn], st[maxn][maxn][maxm];
void init_st() { Log[0] = -1;
    for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) st[i][j][0] = a[i][j];
    for (int k = 1; k <= m; ++k)
        for (int i = 1; i + (1 << k) - 1 <= n; ++i)
            for (int j = 1; j + (1 << k) - 1 <= n; ++j) {
                st[i][j][k] = min(st[i][j][k - 1], st[i][j + (1 << k - 1)][k - 1],
                                  st[i + (1 << k - 1)][j][k - 1],
                                  st[i + (1 << k - 1)][j + (1 << k - 1)][k - 1]);
            }
}

int query(int x1, int y1, int x2, int y2) {
    int k = Log[x2 - x1 + 1];
    return min(st[x1][y1][k], st[x1][y2 - (1 << k) + 1][k],
               st[x2 - (1 << k) + 1][y1][k],
               st[x2 - (1 << k) + 1][y2 - (1 << k) + 1][k]);
}

例题

静态区间最大值

Luogu P3865 【模板】ST表

利用二维st表建图

bzoj 3577: 玩手机