范围最值查询

维基百科,自由的百科全书
跳转至: 导航搜索

范围最值查询(Range Minimum Query),是针对数据集的一种条件查询。若给定一个数组 A[1, n],范围最值查询指定一个范围条件 i 到 j,要求取出 A[i, j] 中最大/小的元素。

若 A = [3, 5, 2, 5, 4, 3, 1, 6, 3],条件为 [3, 8] 的范围最值查询返回 1,它是子数组 A[3, 8] = [2, 5, 4, 3, 1, 6]中最小的元素。

通常情况下,数组 A 是静态的,即元素不会变化,例如插入、删除和修改等,而所有的查询是以在线的方式给出的,即预先并不知道所有查询的参数。

RMQ 问题有预处理 之后每次查询 的算法[1]

范围最值查询问题(RMQ)与最近公共祖先 (图论)(LCA)问题有直接联系,它们可以互相转化。RMQ 的算法常常应用在严格或者近似子串匹配等问题的处理中。

算法[编辑]

Sparse Table[编辑]

建立一个二维数组 的整数值。

在这个数组中 表示范围 中的最大值(例如 中的最大值被计为 )。

建立数组的过程可以在 时间内完成。具体算法类似于动态规划。以下是 C++ 语言描述的代码,数组约定从 0 开始:

void Initialise(vector<int> &Array)
{
	int Length = (int)Array.size();

	// 长度为 0 时,表示数据自身。
	for (int i = 0; i < Length; ++i) F[i][0] = Array[i];
	
	for (int j = 1; (1 << j) <= Length; ++j)
		for (int i = 0; i + (1 << j) - 1 < Length; ++i)
			F[i][j] = min(
				F[i][j - 1], F[i + (1 << (j - 1))][j - 1]
			); // 分成长度相等的两段
}

当我们需要计算一个区间中的最大值(例如 时),我们先求出这个区间的长度(即 8 - 3 + 1 = 6)。

然后我们算出不大于它的最大 值的指数(即 2)。我们要查询分别以 3 开头,和以 8 结尾的两个长度为 的区间的最大值。

显然 也就是()的最大值就是 的最大值。查询的时间是常数,代码如下:

int Query(int Left, int Right)
{
	int i = 0;
	
	while (1 << (i + 1) <= Right - Left + 1) ++i;
	
	return min(
		F[Left][i], F[Right - (1 << i) + 1][i]
	);
}

整个程序的时间复杂度是 ,Q 为查询数。

参考资料[编辑]

  1. ^ Fischer, Johannes; Heun, Volker (2007), "A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array.", Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science, 4614, Springer-Verlag, pp. 459–470, doi:10.1007/978-3-540-74450-4_41