客户端基本不用的算法系列:RMQ问题 - ST 算法
今天的算法可能有点难,但是如果我们只需要会使用 RMQ 问题的 ST 算法模板,这种程度就已经可以了!因为 RMQ 问题除了最优解的 ST 算法,剩下的都是高级数据结构的应用,例如:线段树、树状数组、Splay、Treap 甚至是主席树(额,我什么都没有暗示,业界就是这个名字)。好了今天我们从两个角度来解决这个问题。ST 算法和线段树。当然如果你对高级数据结构感兴趣,我也会在以后的文章中更新这个系列。
注意,学 RMQ 问题与图论没有直接关系,而是 Tarjan 算法中其中的一个重要步骤之一。再次验证了高级算法都是由基础的问题排列组合而来!🧐
引子
RMQ 的英文是 Range Maximum(Minimum) Query,翻译过来其实就是区间求最值的意思。问题描述:对于长度为 n 的数列 A,回答若干询问 RMQ(A, i, j)(i, j <= n)
,返回数列A中下标在 [i, j]
里的最小(大)值。
在这个问题中,我们需要关注的是查询操作,查询可能是海量的,所以如果我们对数据进行快速的预处理,然后在外面处理后的数据结构中进行快速查询,其实就是最理想的状态。
另外,注意是“在给定的区间内”,那么则说明区间在后续的查询时没有变化。所以我们可以理解成在区间确定后,我们其实已经拿到了所有查询情况的答案!对于这种对给定范围内求值的算法,我们对其归类为离线算法。(当然对应的还有在线算 法,后面讲 Tarjan 算法时我们再详谈)
我们先来尝试下暴力:
1nums = [3, 2, 4, 5, 6, 8, 1, 2, 9, 7]
2
3def query(l, r):
4 res = nums[0]
5 for i in range(l, r + 1):
6 res = max(res, nums[i])
7 return res
我们发现每一次查询都是一个 O(n)
的操作,在海量的查询面前,效率就十分低下了。或许你觉得 O(n)
还能接受?但是人总是喜新厌旧、择优选择的 🙄 。
ST 算法解决 RMQ 问题
ST 算法的全名是 Sparse Table Algorithm,中文一般管 Sparse Table 称作稀疏表。原理是基于二进制的倍增+动态规划。个人觉得有些难度,所以只要会套版子就好(因为这种算法一般就局限在自己RMQ 问题)。
大概描述一下 ST 算法的两个步骤:
1. 预处理
ST 算法原理上还是动态规划,我们用 a[1...n]
表示待查询的一组数,设 f[i, j]
表示从 a[i]
到 a[i + 2^j - 1]
这个范围内的最大值。也就是说 a[i]
为起点,连续 2^j 个数的最大值。由于元素个数为 2^j 个,所以从中间平均分成两部分,每一部分元素个数刚好为 2^(j - 1) 个,也就是说,把 f[i, j]
划分成 f[i, j - 1]
和 f[i + 2^(j - 1), j - 1]
。
我画个图来描述一下这个场景:
整个区间的最大值一定是左右两部分最大值的较大值,满足动态规划的最优化原理(子状态影响父状态)。很显而易见的状态转移方程:
边界条件是:
这样我们就可以在O(nlogn)的复杂度内预处理 f 结果数组。
我们举一个例子,还用上面暴力求职的数据:[3, 2, 4, 5, 6, 8, 1, 2, 9, 7]
,f[1, 0]
表示第 1 个数起,长度为 2^0 = 1
的最大值,其实就是 3。
同理,f[1, 1] = max(3, 2) = 3
,f[1, 2] = max(3, 2, 4, 5) = 5
,f[1, 3] = max(3, 2, 4, 5, 6, 8, 1, 2) = 8
。规律就是 2 倍增区间。代码实现一下~
1nums = [3, 2, 4, 5, 6, 8, 1, 2, 9, 7]
2
3f = [[0 for _ in range(1, 40)] for _ in range(1, 31)]
4
5
6def rmq_initial():
7 n = len(nums)
8 for i, num in enumerate(nums):
9 f[i][0] = num
10 for j in range(1, 31):
11 for i in range(0, n):
12 if i + (1 << (j - 1)) >= n:
13 break
14 f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1])
查看一下预处理之后的 f
查询数组:
1[3, 3, 5, 8, 8, 0]
2[2, 4, 6, 9, 9, 0]
3[4, 5, 8, 9, 0, 0]
4[5, 6, 8, 9, 0, 0]
5[6, 8, 8, 8, 0, 0]
6[8, 8, 9, 9, 0, 0]
7[1, 2, 9, 0, 0, 0]
8[2, 9, 9, 0, 0, 0]
9[9, 9, 0, 0, 0, 0]
10[7, 0, 0, 0, 0, 0]
这是一个什么东西呢,我们先行(其实是 f
数组的第二个下标)来看:
由于我们确定了第一个下标为 0,则这行的含义就是:
简单概括就是,对于 f[0][a]
来说,代表的就是 max(nums[0....0 + 2^a)
。这是第二个下标的含义。对应的,对于 f[b][0]
来说,代表的就是 max(nums[b - 2 ^ b + 1 ... b])
。好好理解这个数组含义,后面的查询操作就显而易见了。
2. 查询操作
我们继续思考区间最大值问题,假设我要查询 [l, r]
这个区间,那么我们如果找到两个子区间,他们的并集精确覆盖到 [l, r]
是不是就满足要求了?
ST 由于使用2倍增,它的边界不好完美覆盖全部 case,所以我们在查询的时候需要简单的做交集操作来约束范围。在上面对于 f
数组的理解中,我们知道了 f
数组的横纵坐标分别代表首末的边界数值,我们的想法就是:为了满足所有区间均可求,我们使用两个范围,确定其最大值和最小值,只要能完全精准覆盖 [l, r]
即可求得结果。这里我简单证明一下:
我们假设一个中间量 k
,并满足:
然后我们考虑一下 l 开始的 2^k 个数和以 r 结尾的 2^k 个数 这个区间是否可以覆盖我们的 [l, r]
区间。当且仅当:
极限法我们令 k = log(r - l + 1)
,那么在 f
数组中只需要查询:max(f[l][k], f[r - (1 << k) + 1][k])
就可以了,是不是很容易?🙄 (其实一点都不容易,但是一般教程都会这么写,我也就这么写,hhhhh)。
1def rmq_query(l, r):
2 k = math.log(r - l + 1) / math.log(2)
3 return max(f[l][k], f[r - (1 << k) + 1][k])
如此,我们就通过了 O(1) 的方式完成了指定区间任意范围的 RMQ。对于海量数据查询的需求完成了最高度的优化。但是由于 ST 算法需要一个 2 倍增的预处理,所以整体的复杂度在 O(nlogn)。如此评估下来,其实如果查询量极少的情况下,我们用暴力法的时间开销 O(n) 是优于 ST 算法的,但是 ST 是在大量查询的场景下,所以算法也和业务技术方案一样,有适合于业务的,也有不适合于业务的,一切从业务出发来解决问题就好啦~
我们掌握了以上方法,尝试着套着 ST 算法的模版,来 A 道题尝试一下,你会立马发现它的奇妙(能解决问题)!
ST 算法解决 RMQ 问题
我们来看一道 RMQ 的裸题:HDU-5443 The Water Problem
这种题目分两步走,拍上模板,然后写逻辑!HDU 不支持 Python,我们用 C++ 写一版就好啦~
1
2
3
4
5
6using namespace std;
7
8int f[maxn][20];
9
10// 模板
11void rmq_initial(int n) {
12 for (int j = 1; j < 21; ++ j) {
13 for (int i = 0; i < n; ++ i) {
14 if (i + (1 << (j - 1)) >= n) break;
15 f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
16 }
17 }
18}
19
20// 模板
21int rmq_query(int l, int r) {
22 int k = log(r - l + 1) / log(2);
23 return max(f[l][k], f[r - (1 << k) + 1][k]);
24}
25
26int main() {
27 int T, n;
28 cin >> T;
29 while (T --) {
30 scanf("%d", &n);
31 for (int i = 0; i < n; ++ i) {
32 scanf("%d", &f[i][0]);
33 }
34 rmq_initial(n);
35 int l, r, q;
36 scanf("%d", &q);
37 while (q --) {
38 scanf("%d%d", &l, &r);
39 printf("%d\n", rmq_query(l - 1, r - 1));
40 }
41 }
42 return 0;
43}
结尾
RMQ 问题其实还有很多解发,笔者比较常用的就是 ST 算法和线段树。但是 ST 算法无论从空间复杂度、时间复杂度还是代码量上来看,都优于线段树,但是 ST 算法往往只局限在 RMQ 问题,而具有区间操作的线段树的变化更加灵活,并且是在线查询,可以支持数据源的变化。所以在业务场景下,多变性和业务健壮性的工程角度来看,线段树是一个更加不错的选择。下一篇文章我们来讨论如何利用线段树来解决 RMQ 的问题。
本章节习题
UVa-11235 Frequent values
HDU-3486 Interviewe
HDU-2888 Check Corners [Hard]
HDU-3183 A Magic Lamp [Hard]