RMQ问题分析

2024-05-04 06:38

文章标签 分析问题 rmq

本文主要是介绍RMQ问题分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

　　RMQ问题是一类经典问题，在ACM编程竞赛中我们经常会见到它的身影。其中RMQ是Range Minimium/Maxmium Query的缩写形式，代表区间最小/最大值查询。问题描述为：对一个已知长度为n的数组a，给出多组区间[i,j]，对于每个区间给出该区间的最值。该问题需要注意的地方是要处理多组数据。
　　常规解法是直接遍历区间[i,j]对应的数组元素，然后找出所求的最值。该方法在只有一次查询时是最快且有效的，但是一旦有多组查询，如果每次都是孤立的进行查询，那么效率将是低下的。由此有人提出了sparse-table（st）算法，st算法维护一个稀疏矩阵st。st(i,j)表示起点为i，长度为2^j的区间的最值，这个区间为：
　　　　　　　　[i,i+2^j-1]，
显然st(i,0)=a[i]。当j!=0时，2^j为一个正偶数，我们可以将其分为两个严格相连的区间，每个区间的长度为2^(j-1)。这两个区间分别为：
　　　　　　　　[i,i+2^(j-1)-1]，[i+2^(j-1),i+2^j-1]，
这里可能看得有点晕，但是慢慢推导其实很简单，都是纸老虎嘛！有了两个区间之后，原区间的最值就是这两个连续区间的最值，即动态规划的状态转移方程为（假设考虑最大值）：
　　　　　　　　st(i,j)=max{st(i,j-1),st(i+2^(j-1),j-1}。
　　
对于测试用例a=[1,2,3,4,5,6]，st矩阵如下所示：
　　这里写图片描述
　　从中我们可以看出 $i\in[1,6]$ ， $j\in[0,2]$ ，其中2由log(6-1+1)得到，即floor(log(n))。预先将st矩阵计算出来之后，接下来对于每一个查询(L,R)就可以在O(1)的时间完成，即通过floor(log(R-L+1))求出k值，利用k值得出两个区间[L,L+2^k-1]，[R-2^k+1,R]。容易看出这两个区间的长度都为2^k，注意这两个区间不一定严格连续，它们可能会相交。我们在st矩阵中已经将这两个区间的最值保存起来了，因此原区间的最值也就是这两个区间的最值，即：
　　　　　　　　max(L,R)=max{max(L,L+2^k-1),max(R-2^k+1,R)}，
用st矩阵元素表示为：
　　　　　　　　max(L,R)=max{st(L,k),st(R-2^k+1,k)}，
对于上图，查询[2,6]时k=floor(log(6-2+1))=2，此时需要查找最值的两个区间为：
　　　　　　　　[2,5]，[3,6]，
分别对应st矩阵中的元素：
　　　　　　　　st[2,2]，st[3,2]，
因此
　　　　　　　　max(2,6)=max{st[2,2],st[3,2]}=max{5,6}=6。
　　容易看出该算法在预处理时的时间开销为O(nlogn)，之后每次查询时间开销为O(1)，因此总体来看该算法的时间开销是很可观的。下面给出该算法在java语言下的实现：
　　

import java.util.Scanner;public class Main {private static int n;   //数组a长度private static int[] a; //待查询数组aprivate static int st[][];  //st矩阵public static int RMQ(int L,int R)  //花费O(1)时间查询最大值{if(R<L)return -1000000;int k = (int)(Math.log(R-L+1)/Math.log(2)); //分成的区间大小为2^kreturn Math.max(st[L][k], st[R-(int)Math.pow(2, k)+1][k]);}public static void ST() {   //sparse-table算法for (int i = 1; i <= n; i++) {st[i][0] = a[i];        //获取初始值}int t = (int)(Math.log(n)/Math.log(2)); //矩阵列数for (int i = 1; i <=t ; i++) {for (int j = 1; j <= n-(int)(Math.pow(2, i))+1; j++)st[j][i] = Math.max(st[j][i-1], st[j+(int)(Math.pow(2, i-1))][i-1]);}//状态转移方程}public static void main(String[] args) {n = 6;a = new int[n+1];for (int i = 1; i < a.length; i++){a[i] = i;System.out.print(a[i]+" ");}System.out.println();st = new int[n+1][(int)(Math.log(n)/Math.log(2))+1];ST();int L,R;Scanner scan = new Scanner(System.in);while(true){L = scan.nextInt();R = scan.nextInt();System.out.println(RMQ(L,R));}}
}