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]);
}
京公网安备 11010502036488号