美柑の部屋

涙は見せないと誓った。

Loading…

随机查询（一）：RMQ-ST算法

这篇文章中，我以RMQ问题为例，来介绍随机查询类问题。RMQ是Random Maximum/ Minimum Query的简称，顾名思义，是求解区间最值的问题。假设有一个无序的数组arr（大小为n），给定两个下标l和r，让我们求出arr[l]到arr[r]之间元素的最大值或最小值（我们称之为一次查询，即query），我们当然可以直接遍历这些元素，然后将结果输出。但是如果query的次数不是仅仅只有一次，而是成百上千次，难道我们每次输出对应结果的时候都需要遍历一遍相应的区间吗？

答案显然是否定的，这种方法处理每条query的时间复杂度是O(n)，会出现大量的重复计算。而本篇文章要讲的RMQ-ST算法，在经历过一个O(nlogn)的预处理步骤之后，处理每次query的时间复杂度是O(1)。在query数量极大的情况下，RMQ-ST算法的效率肯定是要远远好于最原始的方法的。

一、输入和输出

要解释一个算法，首先明确其输入与输出。RMQ-ST算法的输入分为两部分，首先是一个长度为n的数组，然后是一系列query，每条query包含两个下标l和r。而该算法的输出，则是针对输入的每条query，依次输出arr[l]到arr[r]之间元素的最大值或最小值（本文以最小值为例）。

二、算法概述

上文提到过，RMQ-ST算法需要进行一个O(nlogn)的预处理步骤，该步骤建立了一个表格table（ST是Sparse Table的简称，该算法被命名为RMQ-ST算法正是由此而来），其中：
table[i][0]等于arr[i]；
table[i][1]等于arr[i]到arr[i+1]之间元素（共2个元素）的最小值；
table[i][2]等于arr[i]到arr[i+3]之间元素（共4个元素）的最小值；
table[i][3]等于arr[i]到arr[i+7]之间元素（共8个元素）的最小值；
table[i][k]等于arr[i]到arr[i+2^k-1]之间元素（共2^k个元素）的最小值。

假设我们已经建立好了这样的一张表，当我们接收到一条query，其下标为[i,j]时，我们应该怎么办？
首先，我们可以求出区间长度len=j-i+1，并且可以求出一个最大的k满足2^k <= len。
然后，我们可以将原区间分割为两段，[i,i+2^k-1]和[j-2^k+1,j]，它们长度均为2^k。我们知道，这两段区间的并集肯定完整地覆盖了区间[i,j]（因为我们找到的是一个最大的满足条件的k）。我们只需要求出这两段区间中元素的最小值min1和min2，然后我们就可以知道，区间[i,j]中元素的最小值，就是min1和min2中较小的那一个。（当然这两个区间之间可能有重叠，不过对于求最值的问题来讲，重叠并不影响最终结果。）
我们惊奇地发现，[i,i+2^k-1]和[j-2^k+1,j]这两段区间的最小值都已经被我们记录在表中了，它们分别对应table[i][k]和table[j-2^k+1][k]。所以我们只需要对每条query，从表中获取这两个元素，然后选取这两个元素中较小的那一个，就是这条query对应的结果。这一步的确是O(1)的复杂度。

三、预处理的步骤

说了这么半天，table到底是怎么生成的呢？其实，table的生成利用了动态规划的思想。当我们想要求出table[i][k]的值时，我们的想法是将长度为2^k的当前区间分为两半，每一半长度为2^(k-1)，然后分别获得两半的最小值，并取出两个最小值中较小的那一个。而这两半的最小值，则是我们已经计算出来的table[i][k-1]以及table[i+2^(k-1)][k-1]。我们可以写出该动态规划的状态转移方程：
F(i, 0) = arr[i]；
F(i, k) = min(F(i, k-1), F(i+2^(k-1), k-1))对于k>0。
这个预处理的步骤其实就是生成一个nlogn大小的表格的步骤，所以时间复杂度为O(nlogn)，空间复杂度也为O(nlogn)。

四、完整代码

RMQ-ST 
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

#include <iostream>
#include <vector>
using namespace std;

int getLog(int n){ //返回logn
    int count = 0;
    n = n >> 1;
    while(n){
        n = n >> 1;
        count++;
    }
    return count;
}

int getPower(int n){ //返回2^n。
    return 1 << n;
}

int main(){
    int count;
    scanf("%d", &count); //输入数组的总大小。

    int size = getLog(count)+1;
    vector<vector<int>> table(size, vector<int>(count, 0));
    for(int j=0; j<count; j++) //输入数组的内容，这里直接将内容填充到表格的第一行中了。
        scanf("%d", &table[0][j]);

    int power1 = 1;
    int power2 = 2;
    for(int i=1; i<size; i++, power1 <<= 1, power2 <<= 1) //利用动态规划填充表格的其余内容。
        for(int j=0; j<count+1-power2; j++)
            table[i][j] = min(table[i-1][j], table[i-1][j+power1]);

    int queryCount;
    scanf("%d", &queryCount); //输入查询总量。
    int left, right;
    int len;
    int logT;
    int T;
    for(int j=0; j<queryCount; j++){ //计算每个查询。
        scanf("%d%d", &left, &right);
        len = right - left + 1;
        logT = getLog(len);
        T = getPower(logT);
        printf("%d\n", min(table[logT][left-1], table[logT][right-T]));
    }
    return 0;
}

五、展望

RMQ-ST算法高效地解决了RMQ问题，但是，该算法也有一些局限性：
1. 如果输入数据可能会多次发生变化，该算法在每次变化后，都需要重新生成一次Sparse Table，时间复杂度为O(nlogn)，比较耗时；
2. 如果询问的内容不只局限于最大/最小值，而是涉及到其他内容（比如一段区间内元素的和），该算法便无法解决；
这个时候，就要轮到线段树或者树状数组出马了。我将会在之后的文章中介绍这两种算法。

评论