4

继续我的最后两个问题，“最小范围查询方法（从树到受限 RMQ） ”和“最小范围查询方法（最后步骤） ”

我在 TopCoder 上遵循了本教程，该方法在最后一节中介绍。

现在假设我已经完成了所有工作，并且准备好进行查询。根据教程，这是我应该做的：

i 和 j 在同一个块中，所以我们使用在 P 和 T 中计算的值

例如，如果有这样的块：

000111

最小值当然在第三个 0 中，但如果 i 和 j 像 4 和 6，则第三个 0 不会在查询条件中。我的理解错了吗？

i 和 j 位于不同的块中，因此我们计算三个值：使用 P 和 T 计算从 i 到 i 块末尾的最小值，使用对 A' 的预计算查询，计算 i 和 j 块之间的所有块的最小值，以及来自j的块开始到j，再次使用T和P；最后返回使用您刚刚计算的三个值的总体最小值的位置。

为什么要计算从 i 到 i 块末尾的最小值以及从 j 块开始到 j 的最小值？两者的答案不都在 i...j 之外吗？另外，如果它不像最后一个问题那样完全合适，该怎么做。

4

1 回答 1

3

最小值当然在第三个 0 中，但如果 i 和 j 像 4 和 6，则第三个 0 不会在查询条件中。我的理解错了吗？

这个想法是为每个可能的块中的所有索引对预先计算 RMQ 。因此，无论您在该块中查询什么索引，您都应该始终能够在 O(1) 时间内读取块内两个值的 RMQ。在您在问题中列出的情况下，索引 4 和 6 不包含块最小值这一事实是正确的，但无关紧要。您已经为索引 4 和 6 预先计算了 RMQ。

为什么要计算从 i 到 i 块末尾的最小值以及从 j 块开始到 j 的最小值？两者的答案不都在 i...j 之外吗？另外，如果它不像最后一个问题那样完全合适，该怎么做。

考虑这张图片：

+------+------+------+------+------+------+
| ?i?? | ???? | ???? | ???? | ??j? | ???? |
+------+------+------+------+------+------+
   ^                            ^
   i                            j

如果要求解 RMQ(i, j)，则最小值可能位于以下三个位置之一：

  • 在与 i 相同的块中，在从 i 在其块内的位置到其块末尾的索引处，
  • 在与 j 相同的块中，在从 0 到 j 在其块内的位置的索引处，或
  • 在中间三个街区之一的某个地方。

该算法通过使用预先计算的表来解决前两种情况的问题，然后使用另一种算法来解决第三种情况。这三个中的最小值应该是您的答案。

希望这可以帮助！这绝不是一个简单的算法，所以如果您需要帮助，请随时在这里提出更多问题！

于 2013-02-09T04:51:35.120 回答