RMQ

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));
	}	                  
}

 

评论

1 楼 handong1587 2015-10-06  

代码有一处错.
query函数最后一行return的应该是:
return Math.max(f[begin][count], f[end-(1<<count)+1][count]);