RMQ问题(Sparse-Table算法)

时间:2020-11-28 21:40:16

  范围最值问题(Range Minimum/maximum Query,RMQ)。给出一个哪个元素的数组A1,A2,...An,要求设计一个数据结构,支持查询操作:计算min(AL,AL+1,...,AR)或者max(AL,AL+1,...,AR)。每次都用一个循环来计算显然不够快,这里介绍Tarjan的Sparse-Table算法,它的预处理时间是O(nlogn),查询时间是O(1),因此效率更高。

  令d(i,j)表示从i开始的,长度为2j的一段元素的最小值,可以用递推的方法计算d(i, j): d(i, j) = min(d(i, j - 1), d(i + 2 j -1, j  - 1)}。

  因为长度是2j,因此d数组的大小不超过nlogn。递推代码如下:

 void RMQ_init(const vector<int>& A) {
int n = A.size();
for(int i = ; i < n; i++) {
d[i][] = A[i];//以i开头,长度为1的最小值是A[i]
} for(int j = ; ( << j) <= n; j++) {//再区间范围内枚举次方
for(int i = ; i + ( << j) - < n; i++) {//枚举每一个开头,直到没有长度为2的j的区间
d[i][j] = min(d[i][j - ], d[i + ( << j) - ][j - ]);
}
}
}

  查询时另k为满足2k<=R-L+1的最大整数,则以L开头、以R结尾的两个长度为2k的区间合起来也就覆盖了查询区间[L, R]。查询代码如下:

 int RMQ_query(int L, int R) {
int k = ;
while(( << (k + )) <= R - L + ) k++;//若2的k+1次方<= R - L + 1,则k还可以加1
return min(d[L][k], d[R - ( << k) + ][k]);
}

  下面看一道例题:UVa 11235 Frequent values

  题意是给出一个非降序的整数数组a1,a2,a3...a4,a5,你的任务是对于一系列询问(i, j),回答在此区间中出现次数最多的值所出现的次数。

  刚看可能觉得和区间最值查询没有什么联系,我们仔细分析一下,由于数组是非降序的,可以知道数值相同的元素一定是聚在一起的,我们将整个数组进行游程编码,比如-1,1,1,2,3,3,可以写成(-1,1),(1,2),(2,1),(3,2),其中(a,b)表示有b个连续的a。我们用value[i]和count[i]分别表示第i段的数值和出现的次数,num[p],left[p],right[p],分别表示位置p所在段的编号和左右端点位置。接下来每次查询(L,R)的结果就是以下三个部分的最大值:

  从L到L所在段的结束处的元素个数(即right[L] - L + 1)

  从R所在段的开始处到R处的元素个数(即R - left[R] + 1)

  中间第num[L] + 1段到第num[R] - 1段的count的最大值(终于用到区间查询最大值,在(num[L] + 1, num[R] - 1)中的最大值)

需要注意的特殊情况是:如果L和R在同一段中,则答案是R - L + 1。

  具体参考代码如下:

 #include <cstdio>
#include <cstring>
#include <vector>
using namespace std; const int maxn = + ;
const int maxlog = ; struct RMQ {
int d[maxn][maxlog];//以i为开头,长度为1<<j的最值
void init(const vector<int>& A) {
int n = A.size();
for(int i = ; i < n; i++)
d[i][] = A[i];//初始化
for(int j = ; ( << j) <= n; j++) {
for(int i = ; i + ( << j) - < n; i++) {
d[i][j] = max(d[i][j - ], d[i + ( << (j - ))][j - ]);
}
}
}
int query(int L, int R) {
int k = ;
while(( << (k + )) <= R - L + ) k++;
return max(d[L][k], d[R - ( << k) + ][k]);
}
}; int a[maxn], num[maxn], right[maxn], left[maxn];
RMQ rmq; int main()
{
int n, q;
while(scanf("%d%d", &n, &q) == && n != ) {
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
a[n] = a[n - ] + ;//放置一个哨兵 int start = -;
vector<int> count;
for(int i = ; i <= n; i++) {
if(i == || a[i] > a[i - ]) {//新一段的开始
if(i > ) {
count.push_back(i - start);
for(int j = start; j < i; j++) {
num[j] = count.size() - ;
left[j] = start;
right[j] = i - ;
}
}
start = i;
}
}
rmq.init(count);//将每段值出现的次数作为查询的内容 int L, R, ans;
while(q--) {
scanf("%d%d", &L, &R);
L--;R--;
if(num[L] == num[R])
ans = R - L + ;
else {
ans = max(R - left[R] + , right[L] - L + );
if(num[L] + < num[R])
ans = max(ans, rmq.query(num[L] + , num[R] - ));
}
printf("%d\n", ans);
}
}
return ;
}