1

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

  1. 在路径上添加值
  2. 在路径上获取总和

我正在使用重光分解。n树中有节点和m查询。使用 HLD，当我知道Lowest Common Ancestor时，我可以将任何查询u和v分成两个不同的查询： from utolca和 from vto 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。谢谢你的任何想法！

4

1 回答 1

1

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

  1. 让我们看一下当前路径的最顶层顶点。如果它不是另一个的祖先，我们跳到它，然后去它的父（在树的更高位置寻找 lca）。

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

我们最多访问O(log n)路径，并对其中之一进行二分搜索。所以这种方法的总时间复杂度是O(log n)每个查询。

于 2016-12-13T18:09:55.647 回答