设计一个在 O(logn) 时间内运行的数据结构

Question

我正在审核这个算法课程的工作，并尝试做一些课堂上给出的练习题。这个问题把我难住了，我就是无法理解它。我的解决方案都没有在 O(logn) 时间内出现。谁能帮我解决这个问题吗？

问题： 假设我们以任意顺序给出一个由 n 个值 x1, x2, ... , xn 组成的序列，并且 寻求快速回答以下形式的重复查询：给定任意对 i 和 j 1≤i＜1 j ≤ n，找出 x1, ... , xj 中的最小值。设计一个使用 O(n) 空间并在 O(log n) 时间内回答每个查询的数据结构。

Answer 1

对于输入 a1,a2,a3,...an ，构造一个包含最小值 (a1,..,ak) 和最小值 (ak+1,..,an) 的节点，其中 k = n/2。

递归构造树的其余部分。

现在，如果您想找到 ai 和 aj 之间的最小值：

1. 确定 i,j 的最低共同祖先。让它成为 k
2. 从 i 开始并继续移动直到达到 k。每次迭代时检查子节点是否为左节点。如果是，则比较右子树的最小值并相应地更新当前最小值。
3. 类似地，对于 j，检查它是否是正确的节点......
4. 在节点 k 比较每个子树返回的值并返回最小值

Answer 2

人们想太多了。假设您从列表开始：

47, 13, 55, 29, 56, 9, 17, 48, 69, 15

制作以下列表列表：

47, 13, 55, 29, 56, 9, 17, 48, 69, 15
13,     29,     9,     17,     15
13,             9,             15
9,                             15
9

我将这些列表的构造、正确用法以及它们为原始问题提供答案的证明作为练习留给读者。 （这可能不是你的家庭作业，但很可能是某人的家庭作业，而且我不喜欢给出家庭作业问题的完整答案。）

Answer 3

我认为关键的一步是您需要事先对数据进行排序。然后您可以将数据存储在数组/列表中。然后，您可以在 O(logn) 中运行快速二分搜索，选出满足条件的第一个值（我假设您的意思是在 xi 和 xj 之间，而不是 x1 和 xj 之间）。

编辑：再想一想，确保该值满足条件可能并不像我想象的那么微不足道

Answer 4

之前以稍微不同的方式提出了这个问题： 对于范围最小查询，我应该使用什么使用 O(n) 存储和 O(log n) 查询时间的数据结构？

尽管如此，为了快速回答，您面临的问题这是一个经过充分研究的——范围最小查询。线段树是一种可以解决 O(N) 空间和 O(logN) 时间要求的问题的数据结构。您可以在此处查看更多详细信息，其中对结构和所涉及的复杂性进行了解释。

Answer 5

尝试解释建议的数据结构：

对于每一对数字，计算并保留较小数字的值。
对于每四个连续数字，计算并保留四个中最小的值。通过选择两对值中较小的一个可以快速完成此操作。
对于每八个连续数字，计算并保留八个中最小的值。
等等。

假设我们想要 x19 到 x65 之间的最小值。

我们查看以下存储值：
x32 到 x63 中最小的一个。
x24 到 x31 中最小的一个。
x20 到 x23 中最小的一个。
x19。
x64 到 x65 中最小的一个。

然后我们选择其中最小的一个。