algorithm - 动态插入和删除树中的边

Question

问题:给定一个包含 N 个节点的有根树 T。每个节点的编号从1到N，节点1是根节点。此外，每个节点都包含一些值。我们必须在给定的树中执行三种查询。

查询 1::
给定一个节点 nd，您必须找到以 nd 为根的子树的所有节点值的总和并打印答案。

查询 2::
给定一个节点 nd，您必须完全删除以 nd 为根的子树(包括节点 nd)。

查询 3::
给定一个节点 nd 和一些整数 v，您必须向节点 nd 添加一个值等于 v 的子节点>。

约束:N 将是 100000 的量级。查询总数也将是 100000 的量级。所以，我不能每次都进行 DFS 遍历。

我的想法:我的解决方案是离线。我将首先找到至少一次添加到树中的所有节点并制作相应的树。然后我将对树进行预序遍历并将其转换为一个数组，其中子树将始终连续出现。那我就可以用线段树数据结构来解决问题了。因此，我的算法将是 O(QlogN)，其中 Q 是查询总数。但是，我正在寻找一种高效的“在线” 解决方案。我的意思是，我会在询问时立即执行每个查询。我不能先存储所有的查询，然后一个一个地执行它们。

非常感谢任何帮助!谢谢。

Answer 1

假设树是平衡的，在每个节点中有两个额外的参数，您可以在 o(qlogn) 中解决它。

每个节点维护一个总和，其值将等于以该节点为根的子树中节点值的总和，并维护父节点。

根据以上两个要求，查询 1 只需返回和加上该节点处的值 (o(1))。查询二减少到仅从该节点的每个父节点减去总和加上该节点的值，直到到达根(o(logn))。查询三只是将 v 添加到该节点的每个父节点，直到到达根节点 (o(logn))。