1

假设有一个包含 N 个整数的大数组：

const unsigned N = 1e12;
int array[N] = { 1, 3 , 8, -5, 4, 3, -1 -6, 6, ....., N};

应该多次查询不同i jindecies范围内的最小元素。返回最小值的复杂度应该小于 O(ji) 并且应该使用少于 O(N^2) 的内存来解决问题。

如何做到这一点？

4

4 回答 4

3

RMQ 的工作方式如下：

我们保留一个数组 M[N][logN]，其中 M[i][j] 显示从 i 开始且长度为 2^j 的最小范围数。为了填充该数组，首先我们计算所有 M[i][0] 值，它们都等于 M[i][0] = A[i]（A[i] 是原始数组）。之后，通过归纳，每个 M[i][j] 将等于min(M[i][j - 1], M[i + (1 << (j - 1))][j - 1])即我们通过取其左右部分的最小值来获得更长间隔的值，这应该在上一步中计算，因为我们从最短到最长的间隔。

之后，为了得到[a..b]区间的最小值，你需要找到最大的P，使得2^P不超过区间[a..b]的长度。答案是min(M[a][P], M[b - (1 << P) + 1][P])

于 2013-03-08T10:40:17.953 回答
2

正如您所提到的，对于静态数组，最快的解决方案是 O(1) 和 O(n) preproc。但在实践中，您可能希望使用以下方法之一，它也适用于动态数组，并且在我看来更容易理解和编码：

  1. 将数组划分为 sqrt(n) 部分，每个部分包含 sqrt(n) 元素，并存储每个部分的最小值。每个 (i,j) 将完全包含其中一些片段，可能还有一些来自左右的元素。传递这些元素并存储片段的答案以找到最小值。这需要 O(n) preproc、O(sqrt(n)) 查询、O(sqrt(n)) 更新和 O(sqrt(n)) 内存。也很容易编码。
  2. 在数组上构建最小段树。这为查询/更新提供了 O(logn)，O(n) 内存/preproc。
于 2013-03-08T11:49:48.493 回答
1

对于那些懂俄语的人，这是解决方案：http ://e-maxx.ru/algo/rmq 对于那些不懂俄语的人，对不起，我没有找到任何东西。如果有人会找到，请编辑我的答案。

于 2013-03-08T10:37:50.837 回答
1

一个简单的解决方案是创建一个二维数组，其中条目 [i, j] 存储范围 arr[i..j] 中的最小值。现在可以在 O(1) 时间内计算给定范围的最小值，但预处理需要 O(n^2) 时间。此外，这种方法需要 O(n^2) 额外空间，这对于大型输入数组可能会变得巨大。

另一种解决方案是构建一个Segment树。Segment树可以在适当的时间内进行预处理和查询。对于分段树，预处理时间为 O(n)，范围最小查询的时间为 O(Logn)。存储段树所需的额外空间是 O(n)。

段树的表示

  1. 叶节点是输入数组的元素。
  2. 每个内部节点代表其下所有叶子的最小值。

Segment树的构建在这里详细解释：

http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

于 2013-03-08T10:41:27.220 回答