java - 使用 O(n log n) 存储和 O(log n) 查询时间的什么数据结构应该用于范围最小查询？

Question

假设给定了一个包含 n 个值 x1、x2 ... xn 的序列，并寻求快速回答以下形式的重复查询:给定 i 和 j，找到 xi ... xj 中的最小值设计一个使用 O(n log n) 空间并在 O(log n) 时间内回答查询的数据结构。

我知道 O(n) 空间和 O(log n) 时间的数据结构的解决方案，但我需要一个答案使用 O( n log n) 空间不少于。

有什么建议吗？

O(n) 空间的解决方案:

O(n) 空间:对于 a1,a2,a3,...an 的输入，构造一个包含 (a1,..,ak) 的最小值和 (ak+1,..,an) 的最小值的节点) 其中 k = n/2。递归构造树的其余部分。现在，如果你想找到 ai 和 aj 之间的最小值: 确定 i,j 的最低共同祖先。让它成为 k 从 i 开始并继续移动直到你击中 k。每次迭代检查子节点是否为左节点。如果是，则比较右子树的最小值并相应地更新当前最小值。类似地，对于 j，检查它是否是正确的节点......在节点 k 比较每个子树返回的值并返回最小值

Answer 1

首先，O(n) 也是 O(n logn)，因此从技术上讲，O(n) 的任何解决方案都是自动 O(n logn)。

您似乎要问的是使用 Θ(n logn) 内存的解决方案(注意 theta )。我不得不说，我认为这是一个有点奇怪的要求，因为您声称您已经拥有更好的 Θ(n) 解决方案。

在任何情况下，您都可以通过制作 log(n) 数据结构的副本。