使用 RMQ 在二叉树中查找 LCA

最低公共祖先 (LCA) 是图论和计算机科学中的一个术语，在树（尤其是二叉树）的上下文中经常使用。树中两个节点的 LCA 被定义为是两个节点共同祖先的最低（最深）的那个节点。

LCA 在二叉树的场景中被广泛用于查找两个节点之间最近的祖先连接。出于多种原因，

这个概念通常用于算法和数据框架中，包括：

1. 二叉树算法：它被用于各种二叉树活动，包括计算两个节点之间的距离，判断某个节点是否是另一个节点的父节点，以及估算连接两个节点的路径。
2. 二叉搜索树中的最低公共祖先：LCA 可以帮助在二叉搜索树中查找具有特定值的两个节点的公共祖先，这对于搜索和检索非常有用。
3. LCA 可用于动态规划解决方案，解决各种与树相关的问​​题，例如确定树的直径或解决关于具有子树查询的树的问题。
4. LCA 用于图算法，例如在通用树（不仅仅是二叉树）中确定两个节点的 LCA。
5. 并行计算：LCA 问题被用作并行计算中的一个基本原语，用于解决其他问题，例如树收缩的类似方法。

RMQ

RMQ 代表“范围最小值查询”(Range Minimum Query)，它与在特定范围内查找数组中最小成员的难度有关。这个问题通常出现在计算机科学和数据结构应用中，包括线段树、稀疏表以及其他与范围查询相关的方法。

以下是对 RMQ 的解释以及如何解决它

给定一个包含 n 个元素的数组 arr 以及由索引 left 和 right（1 基索引）指定的范围，RMQ 问题旨在在子数组 arr[left: right]（包含）中找到最小的元素。

RMQ 解决方案

1. 最直接的技术是遍历给定范围内的元素，并记录最小的元素。由于此方法对于每个查询的时间复杂度为 O(n)，因此对于对大型数组进行频繁查询可能效率不高。

2. 稀疏表方法：解决 RMQ 问题的一种快速方法是预处理数组以创建称为“稀疏表”的数据结构。

- 稀疏表是一个二维数组，其中 table[i][j] 表示从索引 j 开始的长度为 2^i 的范围内的最小成员。

- 这意味着使用以下公式计算表中剩余的条目：对于 i 从 1 到 log2(n)（其中 n 是数组的大小）

- 构建稀疏表后，您可以通过将查询范围分成由稀疏表的不同行覆盖的两个重叠周期，并取相关条目的最小值来以 O(1) 时间回答 RMQ 查询。

3. 线段树方法是解决 RMQ 的另一种标准数据结构。线段树是一棵二叉树，其中每个叶节点代表一个数组元素，每个内部节点存储关于一组项目的信息。为 RMQ 构建线段树的时间复杂度为 O(n)，并且它允许您以 O(log n) 的时间执行 RMQ 查询。

使用 RMQ 在二叉树中查找 LCA 的算法

使用范围最小值查询 (RMQ) 方法在二叉树中查找最低公共祖先 (LCA) 通常涉及一个预处理步骤，以创建数据结构（例如稀疏表），该结构使您能够有效地回答 LCA 查询。以下是在二叉树中查找 LCA 的 RMQ 算法：

1. 预处理：为节点深度创建稀疏表

- 对二叉树进行深度优先遍历 (DFS)，为每个节点分配深度。您可以从根节点（深度为 0）开始，向下遍历树，随着向下而增加深度。

- 在遍历过程中，跟踪您遇到的节点的顺序。这就是构建稀疏表所依据的顺序。

- 将深度和顺序设置为一个一维数组。当 sequence[i] 跟踪在 DFS 过程中遇到第 i 个节点的顺序时，depths[i] 跟踪该节点的级别。

2. 创建深度稀疏表

-创建一个类似于 RMQ 稀疏表的稀疏表，但这次是为节点深度。使用 depths 数组，创建一个二维数组 sparseTable，其中 sparseTable[i][j] 表示范围 [j, j + 2^i - 1] 中的最小深度。

-初始化稀疏表的基例：对于每个 j，sparseTable[0][j] = depths[j]。

- 然后，使用以下公式计算稀疏表中剩余的值：

3. 识别查询 (u, v) 的 LCA

-假设您想计算节点 u 和 v 的 LCA。

-确定这些节点在 DFS 过程中出现的顺序。令 u_order 和 v_order 分别代表节点 u 和 v 的顺序值。

-确保 u_order 等于 v_order。

-确定 k（2^k <= v_order - u_order + 1 的最大整数 k）。

-使用稀疏表在范围 [u_order, u_order + 2^k - 1] 内找到节点 u 和 v 之间深度最小的节点。这可以通过利用稀疏表来实现：

4. 提供 LCA 节点

找到对应于顺序值 lca_order 的节点，作为节点 u 和 v 的 LCA。

Python 代码

此代码使用 RMQ 技术和用于深度的稀疏表，在二叉树中查找两个节点的 LCA。

输出

在二叉树中使用 RMQ 执行 LCA 时，以下是一些关键的注意事项：

效率：RMQ 技术在一次树预处理后，以 O(1) 的时间复杂度找到 LCA，这使得它对于多次 LCA 查询非常高效。

预处理：该方法对二叉树进行深度优先遍历 (DFS)，以构建用于 RMQ 的数据结构（如稀疏表或线段树）。

这些数据结构可以以 O(N log N) 或 O(N) 的时间复杂度创建，其中 N 是树中的总节点数。

多功能性：RMQ 数据结构可以扩展以处理树和数组上的其他基于范围的查询，使其成为算法设计中的宝贵工具。

空间复杂度：RMQ 数据结构，特别是稀疏表和线段树，需要额外的内存来存储辅助数据结构。但是，空间复杂度是实际且可行的。

灵活性：RMQ 技术不仅限于二叉树，还可以用于通用树或其他需要确定节点 LCA 的图结构。

结论

最小查询 (RMQ) 策略是解决这个基本挑战的一种有效方法。这种方法通过一个预处理阶段来查找二叉树中两个节点的 LCA，该阶段会创建一个数据结构（通常是稀疏表或线段树）以辅助快速搜索。

总而言之，利用 RMQ 在二叉树中查找 LCA 是一种稳健且高效的方法，尤其是在同一棵树上有大量 LCA 查询时。它利用数据结构的力量来优化树相关算法和应用中的基本操作。