algorithm - Range Minimum Query 方法(Query)

Question

接上前两个问题“Range Minimum Query approach (from tree to restricted RMQ)”和“Range Minimum Query approach (Last steps)”

我关注了this tutorial在 TopCoder 上，上一节介绍了该方法。

现在假设我已完成所有操作，并且可以进行查询了。根据教程，这是我应该做的:

i and j are in the same block, so we use the value computed in P and T

例如，如果有这样一个 block :

000111

最小值当然在第三个0中，但是如果i和j像4和6一样，第三个0就不会在查询条件中。我的理解有误吗？

i and j are in different blocks, so we compute three values: the minimum from i to the end of i's block using P and T, the minimum of all blocks between i's and j's block using precomputed queries on A' and the minimum from the begining of j's block to j, again using T and P; finally return the position where the overall minimum is using the three values you just computed.

为什么要计算从 i 到 i block 结束的最小值和从 j block 开始到 j 的最小值？两者的答案不都在 i...j 之外吗？另外，如果它不像上一个问题那样完全合适，该怎么办。

Answer 1

The minimum value lies of course in the third 0, but if i and j are like 4 and 6, the third 0 won't lie in the queried criteria. Is my understanding wrong?

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

Why compute the minimum from i to end of i's block and the minimum of start of j's block to j? Don't the answer of both lies outside of i...j? Also, how to do that if it's not entirely a fit just like the last question.

考虑这张图片:

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

如果你想解决 RMQ(i, j)，那么最小值可以在三个地方之一:

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

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

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