稀疏表维护RMQ

  |  

问题

问题:给你一个数组 ,其中有 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