RMQ问题（Sparse-Table算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了RMQ问题（Sparse-Table算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4334字，纯文字阅读大概需要7分钟。
内容图文
范围最值问题（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。递推代码如下：
1 void RMQ_init(const vector<int>& A) {
2 int n = A.size();
3 for(int i = 0; i < n; i++) {
4 d[i][0] = A[i];//以i开头，长度为1的最小值是A[i]
5 }
6
7 for(int j = 1; (1 << j) <= n; j++) {//再区间范围内枚举次方
8 for(int i = 0; i + (1 << j) - 1 < n; i++) {//枚举每一个开头，直到没有长度为2的j的区间
9 d[i][j] = min(d[i][j - 1], d[i + (1 << j) - 1][j - 1]);
10 }
11 }
12 }
查询时另k为满足2k<=R-L+1的最大整数，则以L开头、以R结尾的两个长度为2k的区间合起来也就覆盖了查询区间[L, R]。查询代码如下：
1 int RMQ_query(int L, int R) {
2 int k = 0;
3 while((1 << (k + 1)) <= R - L + 1) k++;//若2的k+1次方<= R - L + 1,则k还可以加1
4 return min(d[L][k], d[R - (1 << k) + 1][k]);
5 }
下面看一道例题：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。
具体参考代码如下：
1 #include <cstdio>
2 #include <cstring>
3 #include <vector>
4 using namespace std;
5
6 const int maxn = 100000 + 10;
7 const int maxlog = 20;
8
9 struct RMQ {
10 int d[maxn][maxlog];//以i为开头，长度为1<<j的最值
11 void init(const vector<int>& A) {
12 int n = A.size();
13 for(int i = 0; i < n; i++)
14 d[i][0] = A[i];//初始化
15 for(int j = 1; (1 << j) <= n; j++) {
16 for(int i = 0; i + (1 << j) - 1 < n; i++) {
17 d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
18 }
19 }
20 }
21 int query(int L, int R) {
22 int k = 0;
23 while((1 << (k + 1)) <= R - L + 1) k++;
24 return max(d[L][k], d[R - (1 << k) + 1][k]);
25 }
26 };
27
28 int a[maxn], num[maxn], right[maxn], left[maxn];
29 RMQ rmq;
30
31 int main()
32 {
33 int n, q;
34 while(scanf("%d%d", &n, &q) == 2 && n != 0) {
35 for(int i = 0; i < n; i++) {
36 scanf("%d", &a[i]);
37 }
38 a[n] = a[n - 1] + 1;//放置一个哨兵
39
40 int start = -1;
41 vector<int> count;
42 for(int i = 0; i <= n; i++) {
43 if(i == 0 || a[i] > a[i - 1]) {//新一段的开始
44 if(i > 0) {
45 count.push_back(i - start);
46 for(int j = start; j < i; j++) {
47 num[j] = count.size() - 1;
48 left[j] = start;
49 right[j] = i - 1;
50 }
51 }
52 start = i;
53 }
54 }
55 rmq.init(count);//将每段值出现的次数作为查询的内容
56
57 int L, R, ans;
58 while(q--) {
59 scanf("%d%d", &L, &R);
60 L--;R--;
61 if(num[L] == num[R])
62 ans = R - L + 1;
63 else {
64 ans = max(R - left[R] + 1, right[L] - L + 1);
65 if(num[L] + 1 < num[R])
66 ans = max(ans, rmq.query(num[L] + 1, num[R] - 1));
67 }
68 printf("%d\n", ans);
69 }
70 }
71 return 0;
72 }
内容总结
以上是互联网集市为您收集整理的RMQ问题（Sparse-Table算法）全部内容，希望文章能够帮你解决RMQ问题（Sparse-Table算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。