常数时间内任何子数组的最大值和最小值

Question

我是一名计算机科学工程专业的学生，​​我在许多任务中都遇到了这个问题。

我得到了一个大小的数组有价值观然后问了一些问题。

在每个查询中我都会得到两个索引在哪里。

我相信，有一种方法可以回答这个问题如果进行了一些预处理。

我必须这样做。

我已经解决这个问题很多天了，但我根本无法解决。

Answer 1

这个问题被称为“范围最小查询”。它经过了充分研究，如果你用 Google 搜索，你最终会得到一个众所周知的、非常聪明的、相当复杂的数据结构，可以满足你的要求，需要 O(N) 空间和预处理时间。

在这里，我将提供一个更简单的解决方案，每当您的数组包含少于 2 ⁶⁴个项目时，该解决方案在实践中都会表现更好......即总是。

我只会谈论寻找最小值，但当然寻找最大值需要类似的结构。

与众所周知的数据结构一样，它使用这个作为组件：

简单的 O(N log N) 空间解决方案

给定一个包含 N 个项目的数组 A，令 M = ceil(log ₂ N)。

^{制作一个大小为 NxM 的矩阵 W，对于每个 (i,j)，其中 0 < i < N 且 1 < j < M，将 W[i][j] 分配给开始的 2 j}个元素中最小值的索引在 A[i] 处，停在数组末尾。

所以现在，对于每个大小为 2 ^j的窗口，我们都有其最小值的索引。由于每个子数组都被最多 2 个重叠窗口精确覆盖，因此我们可以通过检查这 2 个窗口并选择其 2 个最小值中较低的一个来轻松找到任何子数组中的最小值。

初始化该数据结构可以在每个项目的恒定时间内完成。如果您首先计算较小的窗口大小，则可以通过合并 2 个较小窗口的结果来找到每个窗口最小值。

该解决方案需要为每个数组项存储 log N 个索引。

O(N) 空间解

为了使解决方案适合 O(N) 空间，我们需要在 2 个级别上使用前面的数据结构：

1. 将输入分为 64 个元素的块。选择每个块中最小的项目作为其代表。为代表数组实现 O(N log N) 解决方案。假设 N < 2 ⁶⁴，这需要每个块存储少于 64 个索引，即每个项目最多一个索引 - O(N)
2. 对每个块中的 64 个项目分别实施 O(N log N) 解决方案。这需要为每个项目存储最多 6 个索引，大小为 64、32、16、8、4、2。但每个索引只需要 6 位或更少。窗口大小 2 的索引仅占用 1 位。因此，这 6 个索引可以被打包成每个项目一个 32 位字 - 又是 O(N)。（实现注意：仍然在数组末端切断窗口，而不是块末端）

现在，我们每个项目只花费了 8 或 12 个字节（取决于数组索引是 32 位还是 64 位），并且我们可以在恒定时间内轻松回答任何范围最小查询：

• 检查最多 2 个重叠的块代表窗口，以找到查询覆盖的所有完整块内的最小值；
• 最多检查 2 个部分块窗口以覆盖查询的其余部分；
• 返回找到的最小值。