3

假设给定一个包含 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 比较每个子树返回的值并返回 min

4

1 回答 1

3

首先，O(n)is also O(n logn)，所以从技术上讲，任何O(n)自动的解决方案也是O(n logn)。

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

在任何情况下，您都可以通过制作数据结构的副本轻松地将您的Θ(n)解决方案转换为一个解决方案。Θ(n logn)log(n)

于 2013-01-05T15:32:28.893 回答