algorithm - 范围最小查询 <O(n), O(1)> 方法(最后步骤)

Question

接上一题“Range Minimum Query approach (from tree to restricted RMQ)”(推荐阅读)

同样，来自 this tutorial在 TopCoder 上，我有几个问题，我希望有人能解决它们。

所以我将 RMQ(范围最小查询)问题转换为 LCA(最低公共(public)祖先)问题，然后再将其转换回来，我可以得到一个简化的数组。 (两种变换都可以在教程中找到，简化的数组是“从LCA到RMQ”中讨论的数组L)

无论如何，我可以通过使用 Euler Tour 来获取该数组，这是所有计算的核心部分。

首先，我需要通过使整个数组仅包含 1 和 -1 来使其更简单，所以这就是我所做的:Ls[i] = L[i] - L[i-1 ]。

第二步其实就是分区，这很简单，但是有第三步让我很困惑。

Let A'[i] be the minimum value for the i-th block in A and B[i] be the position of this minimum value in A.

A在这句话中指的是L数组，所以最小值永远是1或者-1，而且会有多个1和-1。这让我感到困惑，因为我认为这不会使计算更容易。

第四步，

Now, we preprocess A' using the ST algorithm described in Section1. This will take O(N/l * log(N/l)) = O(N) time and space.

如果A'只保留1s和-1s的记录，在上面做任何事情似乎都没有用。

最后一步，

To index table P, preprocess the type of each block in A and store it in array T[1, N/l]. The block type is a binary number obtained by replacing -1 with 0 and +1 with 1.

这是什么意思？计算每一种组合？比如，000 - 001 -......?

这看起来像是多个问题，但我希望有人可以引导我完成最后这些步骤。谢谢!

Answer 1

希望这有助于解释事情。

A refers to the L array in this sentence, so the minimum value would always be 1 or -1, and there's gonna be multiple 1s and -1s. It confuses me since I don't think this makes calculation easier.

我认为作者在这里混淆了术语。在这种情况下，我认为数组 A 指的是原始值在被预处理为 -1 和 +1 之前的数组。这些值最好放在身边，因为为原始数组的每个 block 计算最小值可以更快地执行 RMQ。稍后会详细介绍。现在，不用担心 +1 和 -1 值。它们稍后发挥作用。

If A' only keep records of 1s and -1s, it would seemed useless to do anything on it.

没错。然而，这里的 A' 保存了每个 block 在被预处理为 -1 和 +1 值之前的最小值，所以这实际上是一个需要解决的有趣问题。同样，-1 和 +1 步骤尚未发挥作用。

To index table P, preprocess the type of each block in A and store it in array T[1, N/l]. The block type is a binary number obtained by replacing -1 with 0 and +1 with 1.

这就是 -1 和 +1 值的用武之地。这一步背后的关键思想是，对于较小的 block ， block 中 -1 和 +1 的可能组合并不多。比如 block 大小是3，那么可能的 block 是

---
--+
-+-
-++
+--
+-+
++-
+++

在这里，我使用 + 和 - 来表示 +1 和 -1。

您正在阅读的文章提供了以下技巧。不要使用 -1 和 +1，而是使用二进制 0 和 1。这意味着可能的 block 是

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

该方案的优点是双重的。首先，由于只有有限多个 block ，因此可以为每个可能的 block 预先计算该 block 内任何一对索引的 RMQ 答案。其次，由于每个 block 都可以解释为一个整数，因此可以将这些问题的答案存储在一个由整数键控的数组中，其中每个整数都是将 block 的 -1 和 +1 值转换为 0 和 1 得到的值。

希望这对您有所帮助!