algorithm - 哪种数据结构/算法可以找到动态 MST(或有根树)路径上的最小节点

Question

在给定的 MST(或有根树)上，我们可以执行以下任务:

1. 给定子树中以 x 为根的所有节点添加值 A。

   [Answered] Using Euclidean path, first and last appearance of x.
   

2. 报告从 i 到 j 的路径上的最大值。

哪种数据结构/算法对这两个查询花费的时间最少？我不需要为此编写代码。我只想知道解决方案背后的想法。

Answer 1

我实现了一个通用的 Sleator--Tarjan 树，它可以提供对数时间操作和其他几个操作(http://www.davideisenstat.com/dtree/)。链接的实现是摊销的，但除了实际效率低下之外，没有理由不能完成最坏情况的版本。如果您考虑自己编写，请与我联系；那里有很多复杂性，对于您的用例来说可能是不必要的。

要在非常高的层次上描述这个想法，需要一个 S--T 树是如何组织的缩略图。我们将树放在某处并将其分解为不相交的路径。每条路径都存储为伸展树(Splay Tree)，其中每个数据结构节点存储其数据结构子树的最大值。 S--T 操作允许对路径集合进行操作以包括查询路径(Expose 和 Evert 一端，然后 Expose 另一端)。 splay 树还允许将一个值添加到它的所有节点(即整个路径)。与原始 S--T 论文相关的技巧是，当前公开的路径以外的路径可以从其父路径延迟更新，从而允许子树更新。

您也可以查看顶层树的实现，但我个人发现顶层树接口(interface)很难推理，而且据我所知，现有的实现在实践中的效率要低得多。