algorithm - 范围最小查询方法（最后步骤）

Question

接我上一个问题“范围最小查询方法（从树到受限RMQ） ”（建议阅读）

同样，在 TopCoder 上的本教程中，我到处都有一些问题，我希望有人能解决它们。

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

无论如何，我可以使用 Euler Tour 得到那个数组，这是所有计算的核心部分。

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

第二步实际上是分区，这很简单，但是第三步让我感到困惑。

令 A'[i] 为 A 中第 i 个块的最小值，B[i] 为该最小值在 A 中的位置。

A指的是这句话中的L数组，所以最小值总是1或-1，并且会有多个1和-1。这让我很困惑，因为我认为这不会让计算变得更容易。

第四步，

现在，我们使用第 1 节中描述的 ST 算法对 A' 进行预处理。这将花费 O(N/l * log(N/l)) = O(N) 时间和空间。

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

最后一步，

为了索引表 P，预处理 A 中每个块的类型并将其存储在数组 T[1, N/l] 中。块类型是通过将 -1 替换为 0 并将 +1 替换为 1 获得的二进制数。

这是什么意思？计算每种组合？比如000———— 001……？

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

Answer 1

希望这有助于解释事情。

A指的是这句话中的L数组，所以最小值总是1或-1，并且会有多个1和-1。这让我很困惑，因为我认为这不会让计算变得更容易。

我认为作者在这里混淆了术语。在这种情况下，我相信数组A指的是原始值数组，然后再将它们预处理为 -1 和 +1。这些值最好放在周围，因为为原始数组的每个块计算最小值使得执行 RMQ 更快。稍后再谈。现在，不要担心 +1 和 -1 值。它们稍后会发挥作用。

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

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

为了索引表 P，预处理 A 中每个块的类型并将其存储在数组 T[1, N/l] 中。块类型是通过将 -1 替换为 0 并将 +1 替换为 1 获得的二进制数。

这就是 -1 和 +1 值的来源。这一步背后的关键思想是，对于小块大小，一个块中 -1 和 +1 的可能组合并不多。例如，如果块大小是 3，那么可能的块是

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

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

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

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

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

希望这可以帮助！