RMQ（范围最小化问题）【倍增法】

问题描述

范围最小化问题（Range Minimum Query，RMQ）。给出一个 n 个元素的数组 $A_1, A_2,\dots,A_n$A1​,A2​,…,An​，设计一个数据结构，支持查询 Query(L, R): 计算 $min{A_L, A_{L+1},\dots,A_R}$minAL​,AL+1​,…,AR​。

解题报告

令 $dp[i][j]$dp[i][j] 表示从 $i$i 开始的，长度为 $2^j$2j 的一段元素中的最小值，则可以用递推的方式计算 $dp[i][j]$dp[i][j]。
$dp[i][j]=min(dp[i][j-1], dp[i+2^{j-1}][j-1])$dp[i][j]=min(dp[i][j−1],dp[i+2j−1][j−1])

为什么 dp[i][j] 表示的是 从 $i$i 开始的，长度为 $2^j$2j 的一段元素中最小值呢？
如果这样的话，就需要在三个区间中找最小值，一方面状态转移方程不好写，另一方面，时间复杂度和空间复杂度并没有提升多少，所以是 $2^j$2j。

注意到 $2^j\le n$2j≤n，因此 d 数组的元素个数不超过 $nlogn$nlogn，而每一项都可以在常数时间计算完毕，故总时间为 $O(nlong)$O(nlong)

查询操作很简单，令 k 为满足 $2^k\le R-L+1$2k≤R−L+1 的最大整数，则以 $L$L 开头、以 $R$R 结尾的两个长度为 $2^k$2k 的区间合起来覆盖了查询区间 $[L,R]$[L,R]。由于是取最小值，有些元素重复考虑了几遍也没有关系。

实现代码

• 预处理

void RMQ_INIT(const vector<int>&A){
	int n= A.size();
	for(int i=0;i<n;i++)dp[i][0]=A[i];
	for(int j=1;(1<<j)<=n;j++){
		for(int i=0;i+(1<<j)-1<n;i++)
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])
	}
}

• 查询

int RMQ(int l, int r){
	int k=0;
	while((1<<(k+1))<=r-l+1) k++;
	return min(d[l][k], d[r-(1<<k)+1][k])
}

参考资料

[1] 算法竞赛·入门经典·训练指南 P197.