哪一种算法最适合在树中找到LCA？

Question

我感兴趣的是在一棵树中找到两个节点的距离，以尽可能少的复杂性。查找过程在树上的一些查询和更新中(添加和删除一个节点)。

该问题可以用LCA作为优化的工具。然而，通过这些帖子，我发现有一些算法可用。

https://cp-algorithms.com/graph/lca.html https://cp-algorithms.com/graph/lca_binary_lifting.html

这是总结，

1. LCA + Sqrt Decomposition

预处理时间: O(N)

查询时间: O(√N)

允许更新树:是

1. LCA +分段Tree

预处理时间: O(N)

查询时间: O(log )

允许更新树:是

1. LCA +稀疏Table

预处理时间: O(N log N)

查询时间: O(1)

允许更新树：No

1. LCA +二进制Lifting

预处理时间: O(N log N)

查询时间: O(log )

允许更新树:是

我的问题是，最好的算法是什么？

或者哪种算法最适合在什么条件下使用？

对于每一种算法，是否还有上述没有提到的其他优点或缺点？

Answer 1

根据个人作为有竞争力的程序员的经验：

• LCA + Sqrt分解--从未使用过此分解--似乎查询时间相当慢，
• LCA+分段树--这是非常好的缺点，唯一的缺点是代码有些乏味--我很少使用它，通常是在一些已经需要段树的问题上(例如，重型轻量级的LCA+稀疏表)--对于某些问题，O(1)查询时间是必需的，尽管它们可能是罕见的
• LCA+二进制提升--我使用了90%的时间--易于编码，而且

也相当快。