RMQ英文是Range Maximum(Minimum) Query,是用来求某个区间的最大值/最小值,通常用在查询次数比较大的区间最值问题中。
RMQ的原理是动态规划,利用了倍增的思想。我们用A[1...N]表示一组数,[Li,Ri]表示题目涉及到的查询区间。
设F[i,j]表示从A[i]到A[i + (2^j) - 1]这个范围的最大值,也就是以A[i]为起点的连续2^j个数的最大值。由于元素个数是2^j,可以均分为两部分,每部分有2^(j-1)个数。整个区间的最大值肯定是前半部分的最大值和后半部分最大值的较大者,满足动态规划的最优子结构。
则动归方程为:F[i, j] = max(F[i, j-1], F[i+2^(j-1), j-1],边界条件:F[i,0] = A[i]。
这样,就可以用nlog2n的复杂度预处理数组。对于查询区间[Li,Ri],先求出满足2^x<=Ri-Li+1的最大的x值。那么[Li,Ri]的最大值为区间[Li, Li+(2^x)-1]和区间[Ri-(2^x)+1,Ri]的较大者,即max(F[Li,x], F[Ri-(2^x)+1,x])。
这样每次查询的时间复杂度与查询区间的长度无关,都是O(1)。
public class RMQ {
private int[] array;
private int[][] f;
private int[][] s;
public void rmq() {
int len = array.length;
int count = 1;
while( (1 << count) <= len)
count++;
f = new int[len][count];
s = new int[len][count];
for (int i = 0; i < len; i++) {
f[i][0] = array[i];
s[i][0] = array[i];
}
for (int j = 1; (1 << j) <= len; j++) {
for (int i = 0; i + (1 << j) - 1 < len; i++) {
f[i][j] = Math.max(f[i][j-1], f[i+(1<<j-1)][j-1]);
s[i][j] = Math.min(s[i][j-1], s[i+(1<<j-1][j-1]);
}
}
}
public int query(int begin, int end) {
int len = end - begin + 1;
int count = 1;
while((1 << count) <= len)
count++;
count--;
return Math.max(f[begin][count], f[end-(1<<count)+1][count-1]);
}
public static void main(String[] args) {
RMQ r = new RMQ();
r.array = new int[] {12,11,99,78,9,0,4,90,2,1};
r.rmq();
System.out.println(r.query(0, 9));
}
}
分享到:
相关推荐
RMQ问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小值下标。
我们会学到RMQ到底是什么东西,并且会知道这样时候的LCA怎么求解,一切尽在其中!
最全的RMQ资料,看懂了应该RMQ没问题了
伊顿主令控制产品按钮和指示灯RMQ16 - 选择指南pdf,现代机器设备的控制面板,即使可用空间有限,也需要传达日益复杂的信息。RMQ16系列紧凑型主令电器为您提供理想的解决方案。按钮头防护等级高达IP65,确保了在恶劣...
上海人民RMQ6 系列自动转换开关产品样本201512pdf,
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
rmq算法,有详细注释 dp1[i][j] = max ( dp1[i][j-1] , dp1[i+(1(j-1))][j-1] ) ; dp2[i][j] = min ( dp2[i][j-1] , dp2[i+(1(j-1))][j-1] ) ;
ACM中的RMQ和LCA问题 对一个区间的最小值询问,也可以是最大值
这是一个关于后缀数组的与RMQ、LCP有关的资料。。。
伊顿按钮和指示灯RMQ16 - 选择指南 (英文版本)pdf,现代机器设备的控制面板,即使可用空间有限,也需要传达日益复杂的信息。RMQ16系列紧凑型主令电器为您提供理想的解决方案。按钮头防护等级高达IP65,确保了在恶劣...
该ppt讲了一种基于线段树的RMQ的ST算法问题和LCA算法,适合初学者用。
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
RMQ是英文Range Maximum(Minimum) Query的缩写,顾名思义是用来求某个区间内的最大值或最小值,通常用在要多次询问一些区间的最值的问题中。
线段树 数据结构 数 统计 RMQ 可以动态查询和添加
http://ybt.ssoier.cn:8088 信息学奥赛一本通(提高篇)测试数据\第4部分 数据结构(提高篇)\第2章 RMQ问题 测试数据
RMQ以及LCA:最近公共祖先 解析及P解法 (ZFrom Internet)
第2章 RMQ-2021-02-07.pdf
3.郭华阳《RMQ与LCA问题》.ppt
上海人民RMQ1 系列自动转换开关产品样本201512pdf,
上海人民RMQ5 系列自动转换开关产品样本201512pdf,