稀疏表(倍增优化DP):区间最值问题

  |  

摘要: 元素不变的区间最值问题,稀疏表

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


给定一个数组,其中的元素可以修改,要查询数组中某个区间的和。过程中需要维护元素修改的操作,并且要高效查询区间的和。用线段树或者树状数组可以解决这个问题,在文章 线段树和树状数组:单点修改、区间查询,区间求和问题 中我们以单点修改为例解决了带修改的区间求和问题。如果整个过程元素没有更新,那么有更好的办法,就是用前缀和进行预处理,然后在预处理出的前缀和数组上高效查询区间和,参考文章 【模板】前缀和与差分

类似的需求还有查询区间的最值。如果数组元素可以修改的话,还是可以考虑线段树或树状数组解决。参考文章 线段树:区间修改、区间查询,区间最值问题树状数组维护区间最值。类似地,如果数组的元素不变,也是有更好的办法,思路也是先预处理,然后在预处理出的中间结果上查询区间的最值。具体的做法是倍增优化 DP,也称为稀疏表。本文我们来看一下这个算法。

区间最值问题

问题:给定一个数组,其中有 $N$ 个数字,对于一次查询,给定区间 [l ,r],返回在这个区间内的最值为多少,一共有 $Q$ 次查询。

主流解法

这种区间最值问题,主流的算法有以下三种,在之前的文章中学习过第一种算法,本文是第二种算法,第三种算法以后有时间再看。

  1. 线段树/树状数组,$O(n)$ 预处理 $O(q\log n)$ 在线查询。
  2. 稀疏表(ST),$O(n\log{n})$ 预处理 $O(q)$ 在线查询。
  3. RMQ标准算法:先规约成LCA,再规约成约束RMQ,$O(n)$ 预处理 $O(q)$ 在线查询。

稀疏表:倍增优化 DP

稀疏表隐含了倍增法的思想。这方面可以参考文章 倍增法

对于区间最值问题,当数组中数据不变时,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