RMQ算法适合求解对一个数组多次查询给定范围内的最值。
预处理操作:
令d[i,j]表示从i开始,长度为2^j的一段元素的最值,可以用递推公式写出d[i,j] = min{ d[i][j-1], d[ i+2^(j-1) ][j-1] }
原理如图所示:
复杂度:因为2^j<=n, 所以d数组的元素不会超过nlogn个, 计算每个d[][]需要O(1)。所以总的时间复杂度是O(nlogn)
查询操作:找到一个最大的整数k,使2^k<=R-L+1,这样查询区间就可以分为 i~i+2^k-1 和 j-2^k+1 ~ j 2个区间。因为是求最值,所以区间有一些重复也没有关系。
//d[i][j] 表示 i往后2^j 区间内的最值
void RMQ_init(int *A,int n)
{
for(int i=; i<n; i++) d[i][]=A[i]; //初始化
// 极端情况 i=0; d[0][j-1]要求(1<<j)-1 < n
for(int j=; (<<j)- < n; j++)
// d[i][j-1] 要求 i+(1<<j)-1 < n
for(int i=; i+(<<j)- < n; i++)
d[i][j]=MAX( d[i][j-], d[i + (<<(j-))][j-] );
} int RMQ(int L, int R)
{
int k=;
while( <<(k+) <= R-L+ ) k++;
// 2段有重合,但是求最值不影响
return MAX( d[L][k], d[R-(<<k) + ][k] );
}