问题：给定包含T节点的根树N每个节点的编号形式为1到N，node1是根节点而且，每个节点都包含一些值我们必须在给定的树中执行三种查询。
问题1：
给定一个节点nd，您必须找到根位于nd的子树的所有节点的值之和并打印答案。
问题2：
给定一个节点，您必须完全删除根在nd的子树（包括nodend）。
问题3：
给定一个节点nd和一些整数nd，您必须将一个子节点添加到值等于v的节点nd。
限制条件：v约为100000。查询总数也将达到100000次所以，我不能每次都遍历DFS。
我的想法：我的解决方案是离线的我将首先找到添加到树中的所有节点（至少一次），并生成相应的树然后，我将对树进行预排序遍历，并将其转换为一个数组，其中的子树将始终连续出现然后我可以使用段树数据结构来解决这个问题。因此，我的算法是o（qlogn），其中q是查询的总数。然而，我正在寻找一个“在线”的解决方案，这是有效的。我的意思是，我已经执行了每一个查询一经要求。我不能先存储所有查询，然后逐个执行它们。
任何帮助都是非常感谢的！
谢谢。
最佳答案
假设树是平衡的，每个节点有两个额外的参数，您可以在o（qlogn）中解决它。
每个节点都保持一个和，其值将等于根在该和上的子树中节点的值之和，同时保持父节点。
有了以上两个需求，查询1只需返回sum加上该节点的值（o（1））。查询2简化为从该节点的每个父节点减去sum加上node的值，直到到达根节点（o（logn））查询3简化为向该节点的每个父节点添加v，直到到达根节点（o（logn））。
关于algorithm - 动态插入和删除树中的边，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23541778/