笔记：RMQ（区间最值）之ST算法

时间：2018-02-04 10:32:37 阅读：238 评论：0 收藏：0 [点我收藏+]

RMQ（区间最值）之ST算法

RMQ即Range Minimum/Maximun Query 中文意思：查询一个区间的最小值/最大值

比如有这样一个数组：A{3 2 4 5 6 8 1 2 9 7}，然后问你若干问题：

数组A下标2~7区间最小的值是多少？最小值是（1）

数组A下标3~6区间最小的值是多少？最小值是（4）

数组A下标1~10区间最小的值是多少？最小值是（1）

......

专业术语：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。

这个问题其实可以用线段树轻松实现O(N)预处理，O（logN）查询，已经是很不错的复杂度了。

但是：有的时候查询操作很多，所以我们需要一个O（1）的查询算法。

那就是Sparse Table 即ST算法

ST算法是比较高效的在线算法。所谓在线算法，是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理，待信息充足以后便可以用较少的时间回答每个查询。ST算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。

（一）首先是预处理，用动态规划（DP）解决。

设A[i]是要求区间最值的数列，F[i, j]表示从从i开始的连续2^j个数中的最大值。（DP的状态）

例如：A数列为：3 2 4 5 6 8 1 2 9 7 12 3 21

下标为：1 2 3 4 5 6 7 8 9 10 11 12 13

F[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是A数列中3这个数。同理：

F[1, 1] = max(3,2) = 3,

F[1，2]=max(3,2,4,5) = 5，

F[3，2]=max(4,5,6,8) = 8， F[3，2]表示从第三个数4开始连续（2^2）4个数中的最大值8

F[1，3] = max(3,2,4,5,6,8,1,2) = 8;

并且我们可以容易的看出F[i,0]就等于A[i]。（DP的初始值）

假如i=3，那么F[i, 0]=max(4,4)=4, A[3]=4, 所以DP的初值就是F[i,0]=A[i]

这样，DP的状态、初值都已经有了，剩下的就是状态转移方程。

我们把F[i，j]平均分成两段（因为F[i，j]一定是偶数个数字），

前半段为 i 到i + 2 ^ (j - 1) - 1， （请动手计算一下）

后半段为i + 2 ^ (j - 1)到i + 2 ^ j - 1 需要注意的是2 ^ (j - 1)和 2 ^ j - 1 的区别

前后段的长度都为2 ^ (j - 1)。

用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。

F[i，j]就是这两段各自最大值中的最大值。

于是我们得到了状态转移方程：

f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]);

方程前半段为f[i,j-1] 表示 从i 起连续2^(j-1)个数的最大值。

方程后半段f[i+2^(j-1),j-1] 表示从i + 2 ^ (j - 1)起连续2^(j-1)个数据的最大值。

然后取前后两段各自最大值中的最大值。

总结：求从i起连续2^j个数的最大值，就是把2^j 分成前后两个2^(j-1)，分别取其最大值，再通过比较获得此状态最大值。

我们先来学习个小知识点“<<”位移符号的使用

C或C++中：

<<可作为左移运算符 (向左移一位，右边自动补0)

比如：i<<4,是按位左移4位。

比如8<<4：

二进制状态下：

0000 0000 0000 1000 = 十进制8

↓

0000 0000 1000 0000 = 十进制128 128=8^4

十进制状态下：

1<<1 等价于 1*2^1

1<<2 等价于 1*2^2

3<<3 等价于 3*2^3

5<<4 等价于 5*2^4

听说位移"<<" 速度比乘法快。

注意+-运算符优先于<<符号

比如：5-1<<1等同(5-1)*2^1 ，而不是5-1*2^1

所以如果要表示 5-1*2^1，要写成5-(1<<1)

DP预处理的代码如下：请选择一种适合自己的方法作为模板。

//第一种写法：请理解好循环条件的意义

int n;  //n是数组元素个数
int a[100004]; //数列
int f[100004][30]; //f[i][j]
//f[i][j]表示以i为起点，区间长度为2^j的一段区间的最小（大）值
void RMQ_ST (  )   ////预处理ST表,数组中共n个元素  O(nlogn)  
{  
for (int i=1;i<=n;i++)   f[i][0]=a[i];//dp初始值
    for(int j=1;j<=20;j++)  //为什么是20? 2^j最大可以是多大？
        for ( int i = 1; i <= n; i++ )  //思考为什么外循环j套i，而不是外循环i套j
            if(i+(1<<j)-1<=n)  //“<<”符号请看前面知识点 (1<<j)注意括号
            {  
              int s=i+(1<<(j-1)); //后半段的起点  等价 i+2^(j-1)
              f [i][j]=max ( f [i][j-1], f [s][j-1] );  //区间最大值，最小值用min函数
            }  
}

//第二种写法：请理解好循环条件的意义

void RMQ_ST2 ( )   //预处理ST表,数组中共n个元素  O(nlogn)
{
for (int i=1;i<=n;i++)   f[i][0]=a[i];  //dp初始值
for (int j=1;(1<<j)<=n; j++)         //注意(1<<j)加上括号
   for (int i=1;i+(1<<j)-1<=n;i++)  //
      f [i][j]=max( f [i] [j-1], f [i+(1<<(j-1))] [j-1] );//求最小值是函数min
 }

这里我们需要注意的是循环的顺序，我们发现外层是j，内层所i，这是为什么呢？

可以是i在外，j在内吗？

答案是不可以。因为我们需要理解这个状态转移方程的意义。

状态转移方程的含义是：我们先得到F[i,0]（即1个元素）的值，然后通过2个1个元素的最值，获得所有长度为F[i,1]（即2个元素的最值），然后再通过2个2个元素的最值，获得所有长度为F[i,2]（即4个元素的最值），以此类推更新所有长度的最值。

而如果是i在外，j在内的话，我们更新的顺序就是F [1,0],F [1,1],F [1,2],F [1,3],表示更新从1开始的1个元素，2个元素，4个元素，8个元素(a[0],a[1],....a[7]）的最值，这跟我们的思维和计算方法完全不同，所以这样的方法肯定是错误的。

为了避免这样的错误，一定要好好理解这个状态转移方程所代表的含义。

（二）接着解决怎么样查询。

先看小知识：

幂：指乘方运算的结果。n^m指将n自乘m次（针对m为正整数的场合）。把n^m看作乘方的结果，叫做“n的m次幂”或“n的m次方”。

其中，n称为“底数”，m称为“指数”（写成上标）。当不能用上标时，通常写成n^m。

对数：如果，即a的x次方等于N（a>0，且a≠1），那么x叫做以a为底N的对数，记作。其中，a叫做对数的底数，N叫做真数。

特别注意：如果在c或c++语言里，注意加上头文件cmath或math.h。

对数形式应该写成x=loga (N)，其中a是底数，(N)是真数，真数N一定要用（）。

比如x=log2 (8),那么x=3。注意：log和2之间不要有空格。

还可以写成另外一种形式：x=log(N) / log(a),真数和底数都要加括号，而且真数在前面，不建议用这个形式。

查询:

假设要查询从(i, j)这一段的最大值, 这个区间的长度我们可以计算得出是j - i + 1。

那么我们先求出一个最大的k, 使得k满足2^k <= (j - i + 1).

我们可以取k=log₂( j - i + 1），举例说明：

要求区间[1，5]的最大值，k =(int)（log2（5 - 1 + 1））= 2。（计算机语言写法）,

(int)是用来向下取整。（想想为什么要向下取整）

我们就可以把[i, j]分成两个(部分重叠的)长度为2^k的区间: [i, i+2^k-1], [j-2^k+1, j];

比如查询数列A：5，6，7，8，9，我们可以查询(1, 4) 和(2, 5)这两个区间。

就是查询5 6 7 8和6 7 8 9 ，原数列左边界i和右边界j是不变的, 只是中间的三个数6 7 8重叠。

又比如数列B： 4 5 6 7 8 9 经计算数列B长度为 j-i+1=6，那么：

k=int(log2(j-i+1))=2 (int)是用来向下取整。（想想为什么要向下取整）

[i, i+2^k-1]区间计算后为[1,4] 包含元素为 4 5 6 7共4个。

[j-2^k+1, j]区间计算后为[3,6] 包含元素为 6 7 8 9 也是4个。

而我们之前dp预处理时已经求出了：

f(i, k)为区间[i, i+2^k-1]的最大值, 比如上面的f(1, 4)我们在预处理时已经求出来了。

f(j-2^k+1, k)为区间[j-2^k+1, j]的最大值，比如上面的f(2, 5)我们在预处理时也已经求出来了。

我们只要返回其中更大的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.

则有：RMQ(A, i, j)=max{ f [i , k], f [ j - 2 ^ k + 1, k]}。(伪代码)

又比如：要求区间[2，8]的最大值，k =(int)( log2（8 - 2 + 1）)= 2，

即求max (f [2, 2]，f [8 - 2 ^ 2 + 1, 2]) = max (f [2, 2]，f[5, 2])；

而f [2, 2]和f[5, 2]在前面已经预处理过了

请计算一下区间[1 ,11]的最大值，像上面一样手写过程。

查询代码如下：

int rmq_ask (int l, int r) //查询区间(l, r)
{
int k=(int) (log2(r-l+1));  
//l->r区间长度---为2^k(向下取整) 千万记住对数一定要整体括起来
    return max (f[l][k], f[r-(1<<k)+1][k]); //根据需要取min或者max
}