RMQ问题的ST解法

RMQ问题：

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A, i , j) (i , j <= n)，

返回数列A中最小(大）值，且该值的下标必须在i,j范围中，也就是说，RMQ问题是指求区间最值的问题。

这个问题有好几种解法，在这里我只讲解ST算法(实质是动态规划)

ST算法是一种在线算法，所谓在线算法，是指用户输入一个查询便能立刻查询到结果，该算法一般用较长的时间

来预处理，待信息充足以后便可以用较少的时间回答每个查询，ST(Sparse Table)算法是一个非常有名的在线处

理RMQ问题的算法，他可以在O(nlogn)时间进行预处理，接着在O(1)的时间回答每个查询。

预处理实质上是动态规划；

在这里RMQ查询数列中的最大值。

首先定义子问题：

从第i个数起，连续2 ^ j个数(包括第 i 个数)中，最大值是多少。

状态：dp[i][j]表示，从第i个数开始，连续 2 ^ j 个数种最大值是多少。

状态方程：

我们分析一下不同状态之间如何转移。

dp[i][j]表示从第i个数开始，连续 2 ^ j 个数种最大值是多少。也就是说

dp[i][j] = max(A[i] , A[i + 1], A[i + 2] .......A[i + 2 ^ (j - 1) -1] ........ A[i + 2 ^ j - 1] )

因此dp[i][0] = A[i],是初值。

我们可以把这一部分平均分为两部分，A[i] ~ A[i + 2 ^ (j-1) -1], A[ i + 2^(j - 1)] ~ A[i + 2 ^ j -1]。

可以很容易的求出这两部分的长度都是 2 ^(j - 1)。所以第一部分的最大值为dp[ i ][ j - 1 ],第二部分的

最大值为dp[ i + 2 ^ (j - 1) ][ j - 1 ]。

因此dp[i][j] = max(dp[ i ][ j - 1 ] , dp[ i + 2 ^ ( j - 1 ) ][ j - 1 ])。

根据状态转移方程可知状态dp[ i ][ j - 1 ],dp[ i + 2 ^ (j - 1) ]必须在dp[i][j]之前，

并且所有的状态都是从dp[i][0]转移过来的。所以在dp的过程中，j应该在外层并从小到大，i在内层并

从小到大。

这一部分代码如下：

代码如下：

void ST()
{
	for(int i = 1 ;i <= n; i++)
	dp[i][0] = A[i] ;
	for(int j = 1; (1 << j) <= n ; j++)		//1<<j 就是 2 ^ j次方，它最大为n;
	{
		for(int i = 1 ; i + (1 << j) -1 <= n; i++)
		{
			dp[i][j] = max(dp[i][j-1],dp[i + (1 << (j - 1))][j-1]);
		}
	} 
	
}

接下来就是查询步骤了：

假如我们要查询区间i, j的最值，那么这个值应该等于dp[i][log2(j - i +1)],但是此时dp[i][log2(j - i +1)]的值

不一定是区间i , j的最值。因为i + 2 ^ log2( j - i +1 ) -1不一定等于 j。比如我要查询区间3 ~ 9的值，那么

log2(9 - 3 +1) = 2,但是 3 + 2 ^ 2 -1 == 6，说明我们查询的实际区间是3 ~ 6,而不是3 ~ 9。

所以在查询中我们可以找到两个区间，这两个区间能正好覆盖i~j的区间。

所以 max(A[i ~ j]) = max ( dp[i][log2(j - i + 1)], dp[k - ( 2 ^ log2(j - i + 1) ) +1][log2(j - i + 1)] )。

k - (2 ^ log2(j - i + 1) +1) + 2 ^ log2( j - i +1 ) -1 == j,所以这两个区间能覆盖区间i~j.(这一段有点绕，

但是你试几组样例就知道为什么这样做了)

这一部分代码如下：

int RMQ(int l, int r)
{
	int k;
	while((1 << (k +1)) <= r - l +1) k++;			//计算 log2(r - l +１) 
	return max(dp[l][k],dp[r - (1 << k) + 1][k]) //保证能覆盖区间l ~ r; 
}

以上是RMQ的ST解法

—————————————————————————————————————————————

例题：

poj 3368 Frequent values

点击打开链接

题意：

给你一个长度为n的非递减数组，并有q次询问，每次询问给你区间i,j;

问在这个区间内出现次数最多的数字的次数有多少？

我们可以对这个区间先进行预处理。

-1 -1 1 1 1 1 3 10 10 10 变为

1 2 1 2 3 4 1 1 2 3

这样我们在查找区间i,j出现次数最多的数字的次数，我们就可以把这个区间分成两部分

一部分是找到预处理之后的数组中这个区间内第一个为1的数，假设这个数的下标为k，

显然答案就为max(k - i,RMQ(k,j));

代码如下：

#include<stdio.h>
#include<algorithm>
using namespace std;

const int INF = 100010;

void ST();

int RMQ(int i ,int j);

int dp[INF][20];

int data[INF], A[INF];

int n,q;

/*
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

Sample Output

    1
    4
    3
*/
int main()
{
	while(scanf("%d", &n) && n != 0)
	{
		scanf("%d", &q);
		
		scanf("%d",&data[1]);
		
		A[1] = 1;
		for(int i = 2; i <= n ;i++)
		{
			scanf("%d",&data[i]);
			
			if(data[i] == data[i-1])
			{
				A[i] = A[i-1] + 1;			//预处理data。注意这不是ST的预处理 
			}
			else
			A[i] = 1;
			
		}
		
		ST();
		
		for(int q1 = 1; q1 <= q; q1++)
		{
			int i , j;
			
			scanf("%d %d", &i, &j);
			
			int k = i ;
			
			while(A[k] != 1 && k <= j)
			k++;
			
			int ans = RMQ(k , j) ;
			
			int result = max(k - i, ans);
			
			printf("%d\n" , result);
			
			
		} 
	
	
	}
	

	
	
	
	return 0;
} 

void ST()
{
	for(int i = 1 ; i <= n; i++)
	dp[i][0] = A[i];
	
	for(int j = 1; (1 << j) <= n; j++)
	{
		for(int i =1; i + (1 << j) -1 <= n; i++)
		{
			dp[i][j] = max(dp[i][j-1], dp[i + (1 << (j-1))][j-1]);
		}
	}
	
	
	
}

int RMQ(int i, int j)
{
	if(i > j)
	return 0; 
	int k = 0;
	
	while((1<<(k + 1)) <= j -i +1)k++;			// k 为log2(j - i + 1) 
	
	return max(dp[i][k], dp[j - (1 << k) + 1][k]);
	
}