ACM►数据结构►ST表

二维ST表

ST表

ST 表可以 $O(N\log N)$ 的预处理一位的区间信息，然后 $O(1)$ 的进行查询。

二维 ST 表类似，可以 $O(nm\log n \log m)$ 的预处理一个二维矩阵的子矩阵信息，并且 $O(1)$ 的查询。

代码

下面拿 CF713D 为例，题目需要维护二维的区间最大值。

ans[i][j][a][b]的含义为以 $(i, j)$ 为左上角 $(i + 2^a - 1, j + 2^n - 1)$ 为右下角的子矩阵的区间信息。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1005;
const int INF = 0x3f3f3f3f;

int data[MAX][MAX], dp[MAX][MAX], csum[MAX][MAX], rsum[MAX][MAX];

int n, m;

void solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (data[i][j]) {
                rsum[i][j] += rsum[i - 1][j] + 1;
                csum[i][j] += csum[i][j - 1] + 1;
            } else {
                rsum[i][j] = csum[i][j] = 0;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = data[i][j] ? 1 : 0;
            if (dp[i - 1][j - 1]) {
                int v = dp[i - 1][j - 1];
                int c = csum[i][j];
                int r = rsum[i][j];
                dp[i][j] = min(v + 1, min(r, c));
            }
        }
    }
}

int low_log[MAX];

void init() {
    int cnt = 0, now = 1;
    for (int i = 1; i < MAX; i++) {
        if (now * 2 <= i) cnt++, now *= 2;
        low_log[i] = cnt;
    }
}

int ans[MAX][MAX][10][10];

void cal() {
    for (int x = 0; x < 10; x++) {
        for (int y = 0; y < 10; y++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (x + y == 0) {
                        ans[i][j][0][0] = dp[i][j];
                        continue;
                    }
                    int dx = x > 0 ? (1 << (x - 1)) : 0;
                    int dy = y > 0 ? (1 << (y - 1)) : 0;
                    int ox = max(0, x - 1);
                    int oy = max(0, y - 1);

                    int A = ans[i][j][ox][oy];
                    int B = i + dx > n ? 0 : ans[i + dx][j][ox][oy];
                    int C = j + dy > m ? 0 : ans[i][j + dy][ox][oy];
                    int D = (i + dx > n || j + dy > m) ? 0 : ans[i + dx][j + dy][ox][oy];

                    ans[i][j][x][y] = max(max(A, B), max(C, D));
                }
            }
        }
    }
}

int query(int x1, int y1, int x2, int y2) {
    int px = low_log[x2 - x1 + 1];
    int py = low_log[y2 - y1 + 1];
    int dx = (1 << px) - 1;
    int dy = (1 << py) - 1;
    return max(max(ans[x1][y1][px][py], ans[x2 - dx][y1][px][py]),
               max(ans[x1][y2 - dy][px][py], ans[x2 - dx][y2 - dy][px][py]));
}

bool ok(int mid, int x1, int y1, int x2, int y2) {
    if (mid == 0) return true;
    return query(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid;
}

int main() {
    init();
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &data[i][j]);
        }
    }
    solve();
    int q;
    scanf("%d", &q);
    cal();
    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        int l = 0, r = min(y2 - y1 + 1, x2 - x1 + 1), ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (ok(mid, x1, y1, x2, y2)) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
}