算法基础算法

稀疏表维护RMQ

字数统计: 935字   |   阅读时长: 4分
, , ,

问题

问题：给你一个数组 ，其中有 N 个数字，现在给你一次查询，给你区间[l ，r]，问你在这个区间内的最值为多少

数组长度为 N，查询次数为 Q

主流解法

1、搜索，$O(n)$ 预处理 $O(qn)$ 在线查询。

2、稀疏表(ST)，$O(n\log{n})$ 预处理 $O(q)$ 在线查询。

3、线段树/树状数组，$O(n)$ 预处理 $O(qlogn)$ 在线查询。

4、RMQ标准算法：先规约成LCA，再规约成约束RMQ，$O(n)$ 预处理 $O(q)$ 在线查询。

这里关注稀疏表这种做法

稀疏表

适用与数组中的数据保持不变的情况

稀疏表隐含了倍增法的思想。倍增法

当数组中数据不变时，RMQ 算法一般用较长时间$O(N\log N)$做预处理，然后可以在 $O(1)$ 的时间内处理每次查询。该方法称为稀疏表。
这种先预处理，在查询的做法与用前缀和处理大量区间和查询的思想相同。

st_table

<1> 预处理部分

1
dp[i][j] := 从第 i 位开始，连续 2^j 个数的最小值

例如: arr = [1, 2, 6, 8, 4, 3, 7]

dp[2][1] 表示从第2位数开始连续2个数的最小值，即2,6中的最小值，所以 dp[2][1] = 2;
dp[3][2] 表示从第3位数开始连续4个数的最小值，即6,8,4,3中的最小值，所以 dp[3][2] = 3
dp[i][0] 表示第i个数字本身

求 dp[i][j] 的时候可以把它分成两部分，第一部分是从 $i$ 到 $i+2^{j-1}-1$ ，第二部分从 $i+2^{j-1}$ 到 $i+2^{j}-1$。

因为二进制数前一个数是后一个的两倍，所以可以把 $i$ 到 $i+2^{j}-1$ (即 dp[i][j] 表示的区间范围) 这个区间通过 $2^{j-1}$ 分
成相等的两部分，进而写出转移方程：

1
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1])

在外层枚举 j : 1..(1<<j)<=N，含义：
先更新每两个($2^{1}$)元素中的最小值，然后通过每两个元素的最小值获得每4个元素中的最小值，依次类推更新所有长度的最小值。

<2> 查询部分

查询区间 [l, r]，令 $k = log_{2}(r - l + 1)$，则区间 [l, r] 的最小值计算如下 

1
query(l, r) = min(dp[l][k], dp[r - (1 << k) + 1][k])

因为 dp[l][k], dp[r - (1 << k) + 1][k] 分别维护区间 [l, $l + 2^{k} - 1$] 和 [$r - 2^{k} + 1$, r]。而 $l + 2^{k} - 1 \geq r - 2^{k} + 1$

代码(C++)

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
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class RMQ
{
public:
    RMQ(){}

    void init(const vector<int>& arr)
    {
        int n = arr.size();
        // 2 ^ m <= n
        // log2(2^m) <= log2(n)
        // m <= log2(n)
        int m = log2(n);
        dp.assign(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; ++i)
            dp[i][0] = arr[i]; //初始化
        for(int j = 1; (1 << j) <= n; ++j)
            for(int i = 1; i + (1 << j) - 1 <= n; ++i)
                dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }

    int query(int l, int r)
    {
        int k = log2(r - l + 1);
        return min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }
private:
    vector<vector<int>> dp;
};

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i)
        cin >> arr[i];
    cout << "数据: " << endl;
    for(int i = 0; i < n; ++i)
        cout << i << "  " << arr[i] << endl;
    RMQ rmq;
    rmq.init(arr);
    while(true)
    {
        int start, end;
        cin >> start >> end;
        cout << "查询区间: [" << start << ", " << end << "], 最小值：";
        cout << rmq.query(start, end) << endl;
    }
};
Share