我在一次比赛中遇到了这个问题(现在已经结束)，我想不出一个节省时间的算法。
给你一个有 N ( <=10^5) 个节点的有根树。最初所有节点的值为 0。将对树进行 M 次更新 (<=10^5)，其形式为
Add x y – 将 y 添加到节点 x 。
AddUp x y – 将 y 添加到 x，x 的父级，x 的父级的父级，直到根。
之后会有 Q 个查询(<=10^5)个查询，您将被要求提供节点的值或以该节点为根的子树的总和。
我做了什么:-
首先我尝试了根据操作更新每个节点的朴素算法，但显然这很花时间。
我也想过使用线段树和延迟传播，但想不出合适的方法。
感谢任何帮助，谢谢!
最佳答案
首先，构建一个图表，其中 child 指向他们的 parent 。 之后，解析所有更新并将 Add 和 AddUp 的总和分别存储在树的每个节点中。 您的节点应具有以下变量:
sum_add : the sum of all the Add of this node
sum_add_up : the sum of all the AddUp of this node
subtree_sum : the sum of the subtree. Initialize with 0 by now.
现在，使用拓扑顺序横向处理您的图，即，如果节点的所有子节点都已被处理，您将只处理一个节点，这需要 O(N)。现在让我定义过程函数。
process(V) {
V.sum_add_up = V.sum_add_up + sum(sum_add_up of all V.children)
V.subtree_sum = V.sum_add + V.sum_add_up + sum(subtree_sum of all V.children)
}
现在您可以在 O(1) 中回答所有查询。查询一个节点V的值是V.sum_add + V.sum_add_up，查询V的子树就是V.subtree_sum.
关于c++ - 树中路径的范围查询，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46915778/