algorithm - 如何使用 HLD 查找 LCA？

Question

我有一棵树。我想回答以下问题:

1. 在路径上增加值(value)
2. 获取路径上的总和

我正在使用重光分解。树中有 n 个节点和 m 个查询。使用 HLD，当我知道最低公共(public)祖先时，我可以将对 u 和 v 的任何查询分成两个不同的查询:来自 u 到 lca 和从 v 到 lca。因此，查询将在 O(log^2n) 时间内得到答复(log 从 u 和 v 到 lca，以及 log 用于重路径上的线段树)。

如您所知，HLD 是在 O(n) 时间内构建的，因此，总时间为 O(n + m*log^2n)。我的问题是如何使用已经构建的 HLD 找到 LCA。我不能发明算法。

我可以使用二进制爬升来获得 LCA，但它需要 O(nlogn) 预处理，这会使渐近行为变得更糟。我也可以使用 Range Minimum Query，这不会浪费时间，但我想在此过程中使用 HLD。感谢您的任何想法!

Answer 1

假设我们知道如何检查一个节点是否是另一个节点的祖先(我们可以通过在深度优先遍历期间预先计算进入和离开每个顶点的时间来做到这一点)。这个想法是从一个顶点跳起来找到lca。

1. 让我们看一下当前路径的最高顶点。如果它不是另一个的祖先，我们跳转到它，然后转到它的父级(在树中更高的地方寻找 lca)。

2. 否则，lca 就在这条路径上的某个地方。我们可以对它进行二进制搜索(它是最低的顶点，因此它是另一个顶点的祖先)。

我们最多访问 O(log n) 路径，然后对其中一个路径进行二分查找。因此，此方法的总时间复杂度为每个查询 O(log n)。