RMQ原理及实现

2018/10/03 10:19
阅读数 32

  RMQ(Range Minimum/Maximum Query),区间最值查询问题,是指:对于长度为n的数列A,回答若干次询问RMQ(i,j),返回数列A中下标在区间[i,j]中的最小/大值。

  这里介绍Tarjan的Sparse-Table算法,预处理时间为O(nlogn),但查询只需要O(1),并且常数很小,算法也很容易写出。

 1)预处理:

  设A[i]是要求区间最值的数列,d[i, j]表示从第i个数起连续2^j个数中的最小值。(DP的状态)

  显然d[i][0]的值就是A[i](DP初值),我们把d[i,j]平均分成两段(因为d[i,j]一定是偶数个数字),从 i 到i + 2 ^ (j - 1) - 1为一段,i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。于是我们得到了状态转移方程d[i, j]=min(d[i,j-1], d[i + 2^(j-1),j-1]),代码实现如下(这里使用lrj蓝书代码):

1 void RMQ_init(const vector<int> &A) {
2     int n = A.size();
3     for(int i = 0; i < n; ++i) d[i][0] = A[i];
4     for(int j = 1; (1 << j) <= n; ++j) 
5         for(int i = 0; i + (1 << j) - 1 < n; ++i) 
6             d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
7 }

2)查询:

  假如我们需要查询的区间为(i,j),那么我们需要找到覆盖这个闭区间(左边界取i,右边界取j)的最小幂(可以重复,比如查询1,2,3,4,5,5不是2的任意次方,但我们可以查询1234和2345)。

  这个查询长度我们取范围小于等于区间长度的最大(2^k),这样我们查询i到 i +(2^k)与j - (2^k) + 1到j的值,取二者最小值即可,代码实现如下:

1 int RMQ(int L, int R) {
2     int k = 0;
3     while((1 << (k + 1)) <= R - L + 1) ++k;
4     return min(d[L][k], d[R - (1 << k) + 1][k]);
5 }

 

展开阅读全文
rmq
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部