前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >客户端基本不用的算法系列:RMQ问题 - ST 算法

客户端基本不用的算法系列:RMQ问题 - ST 算法

作者头像
用户2932962
发布2019-07-17 20:21:44
1.1K0
发布2019-07-17 20:21:44
举报
文章被收录于专栏:程序员维他命

今天的算法可能有点难,但是如果我们只需要会使用 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 算法时我们再详谈)

我们先来尝试下暴力:

代码语言:javascript
复制
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) = 3f[1, 2] = max(3, 2, 4, 5) = 5f[1, 3] = max(3, 2, 4, 5, 6, 8, 1, 2) = 8。规律就是 2 倍增区间。代码实现一下~

代码语言:javascript
复制
 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 查询数组:

代码语言:javascript
复制
 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)。

代码语言:javascript
复制
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++ 写一版就好啦~

代码语言:javascript
复制
 1#include <iostream>
 2#include <cstdio>
 3#include <math.h>
 4#define maxn 1000000 + 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]
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员维他命 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 引子
  • ST 算法解决 RMQ 问题
    • 1. 预处理
      • 2. 查询操作
      • ST 算法解决 RMQ 问题
      • 结尾
      • 本章节习题
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档