范围最小查询方法（从树到受限RMQ）

范围最小查询 方法（从树到受限RMQ）

这是我目前对让您感到困惑的事情的理解：

1. 为了将RMQ减少为LCA，您需要将阵列转换为树，然后对该树进行Euler游览。
2. 为了进行Euler游览，您需要存储树，使得每个节点都指向其子节点。
3. 从RMQ到LCA列出的缩减每个节点都指向其父节点，而不是其子节点。

如果是这种情况，您的顾虑是完全合理的，但是有一种简单的方法可以解决此问题。具体来说，一旦有了所有父指针的数组，就可以将其转换为树，其中每个节点在O（n）时间内指向其子节点。这个想法如下：

• 创建一个n个节点的数组。每个节点都有一个值字段，一个左子节点和一个右子节点。
• 最初，将第n个节点设置为具有左子级无效，右子级无效以及数组中第n个元素的值。
• 遍历T数组（其中T [n]是n的父索引）并执行以下 *** 作：
  • 如果T [n] = *，则第n个条目是根。您可以将其存储以备后用。
  • 否则，如果T [n] <n，则您知道节点n必须是其父节点的右子节点，该父节点存储在位置T [n]。因此，将第T [n]个节点的右子节点设置为第n个节点。
  • 否则，如果T [n]> n，则您知道节点n必须是其父节点的左子节点，该子节点存储在位置T [n]中。因此，将第T [n]个节点的左子节点设置为第n个节点。

由于每个节点仅被处理一次，因此运行时间为O（n）。

完成此 *** 作后，您已经明确构建了所需的树结构，并具有指向根的指针。从那里开始，继续进行算法的其余部分应该相当简单。

希望这可以帮助！