【数据结构】RMQ

引言

RMQ是对静态区间的一种查询结构，一般用于求区间最大或最小值。

RMQ需要nlogn时间预处理，查询O(1)。

空间复杂度较高，为nlogn，所以有些题可能没法开下这么大的数组，这时候就可以考虑写线段树了。

RMQ

思想

RMQ思想很简单，就是倍增思想。

设f[i][j]表示[i,..,i+2^j-1]区间中的最大值，那么f[i][j]就等于max(f[i][j-1],f[i+2^(j-1)][j-1])。

实现

求log，直接用对数函数计算太慢，这里有一种简单有效的方法：

1
2
3
for (int i = 1; i < N; i++) {
        lg[i] = i >> lg[i - 1] + 1 ? lg[i - 1] + 1 : lg[i - 1];
    }

预处理：

1
2
3
4
5
for (int i=1; i<=n; i++)
    pmax[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j++)
    for(int i = 1; i + (1 << j) - 1 <= n; i++)
        pmax[i][j] = max(pmax[i][j-1], pmax[i + (1 << (j - 1))][j - 1]);

查询：

1
2
3
4
int maxrmq(int l, int r) {
    int k = lg[r - l + 1];
    return max(pmax[l][k], pmax[r - (1 << k) + 1][k]);
}

应用

POJ2019，二维RMQ，和一维原理一样，只是多两层循环罢了～

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define N 260
#define LN 9

int rmax[N][LN][N][LN], rmin[N][LN][N][LN];
int lg[N];
int n, b, q;
int a[N][N];

void init_rmq() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            rmax[i][0][j][0] = rmin[i][0][j][0] = a[i][j];

    for (int k = 1; (1 << k) <= n; k++)
        for (int p = 1; (1 << p) <= n; p++)
            for (int i = 1; i + (1 << k) - 1 <= n; i++)
                for (int j = 1; j + (1 << p) - 1 <= n; j++) {
                    rmax[i][k][j][p] = max(max(rmax[i][k - 1][j][p - 1], rmax[i][k - 1][j + (1 << (p - 1))][p - 1]), max(rmax[i + (1 << (k - 1))][k - 1][j][p - 1], rmax[i + (1 << (k - 1))][k - 1][j + (1 << (p - 1))][p - 1]));
                    rmin[i][k][j][p] = min(min(rmin[i][k - 1][j][p - 1], rmin[i][k - 1][j + (1 << (p - 1))][p - 1]), min(rmin[i + (1 << (k - 1))][k - 1][j][p - 1], rmin[i + (1 << (k - 1))][k - 1][j + (1 << (p - 1))][p - 1]));
                }
}

int ask_rmq_max(int lx, int ly, int rx, int ry) {
    int dx = lg[rx - lx + 1];
    int dy = lg[ry - ly + 1];
    return max(max(rmax[lx][dx][ly][dy], rmax[lx][dx][ry - (1 << dy) + 1][dy]), max(rmax[rx - (1 << dx) + 1][dx][ly][dy], rmax[rx - (1 << dx) + 1][dx][ry - (1 << dy) + 1][dy]));
}

int ask_rmq_min(int lx, int ly, int rx, int ry) {
    int dx = lg[rx - lx + 1];
    int dy = lg[ry - ly + 1];
    return min(min(rmin[lx][dx][ly][dy], rmin[lx][dx][ry - (1 << dy) + 1][dy]), min(rmin[rx - (1 << dx) + 1][dx][ly][dy], rmin[rx - (1 << dx) + 1][dx][ry - (1 << dy) + 1][dy]));
}

int main() {
    for (int i = 1; i < N; i++) {
        lg[i] = i >> lg[i - 1] + 1 ? lg[i - 1] + 1 : lg[i - 1];
    }
    while (scanf("%d%d%d", &n, &b, &q) != EOF) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        init_rmq();
        int x, y;
        while (q--) {
            scanf("%d%d", &x, &y);
            printf("%d\n", ask_rmq_max(x, y, x + b - 1, y + b - 1) - ask_rmq_min(x, y, x + b - 1, y + b - 1));
        }
    }
    return 0;
}

（待更新…）