algorithm - 更新树并跟踪某些子树节点的变化

Question

问题:
给定一棵有根树，其中每个节点从 1 到 N 编号。最初每个节点包含一些正值，比如 X。现在我们要对树执行两种类型的操作。总 100000 操作。

第一种:

Given a node nd and a positive integer V, you need to decrease the value of all the nodes by some amount. If a node is at a distance of d from the given node then decrease its value by floor[v/(2^d)]. Do this for all the nodes.
That means value of node nd will be decreased by V (i.e, floor[V/2^0]). Values of its nearest neighbours will be decreased by floor[V/2] . And so on.

第二种:

You are given a node nd. You have to tell the number of nodes in the subtree rooted at nd whose value is positive.

注意:树中的节点数最多可达100000，节点中的初始值X最多可达1000000000。但是要执行减量操作的 V 的值最多为 100000。

如何有效地完成这项工作？我被这个问题困扰了很多天。感谢您的帮助。

我的想法:我正在考虑离线解决这个问题。我将首先存储所有查询。然后，如果我能以某种方式找到某个节点 nd 的值变得小于或等于零的时间[在哪个操作之后](比如 death time，对于每个和每个节点。然后我们可以进行某种二进制搜索(可能使用二进制索引树/线段树)来回答所有第二种类型的查询。但问题是我无法找到死亡时间 对于每个节点。

我也尝试使用 Heavy Light Decomposition 在线解决它，但我也无法使用它解决它。

谢谢!

Answer 1

给定一棵具有顶点权重的树，存在一个顶点，当该顶点被选为根时，其子树的权重最多为总数的一半。这个顶点是一个“平衡分隔符”。

这是一个时间复杂度为 O((n + k) polylog(n, k, D)) 的算法，其中 n 是顶点数，k 是操作数，D 是最大减少量。在第一阶段，我们计算每个顶点的“死亡时间”。第二，我们计算事件顶点。

要计算死亡时间，首先将每个减少操作拆分为 O(log(D)) 个减少操作，其参数是 1 和 2^floor(lg(D)) 之间的 2 次方(含)。递归地执行以下操作。令 v 为平衡分隔符，其中顶点的权重为一加上对其的减少操作数。计算与 v 的距离，然后确定，对于每次和每个 2 的幂，使用该有效参数对 v 进行的累积操作数(即，如果距 v 距离为 2 的顶点减少 2^i，则记录 a - v) 的 2^(i - 2) 系数发生 1 次变化)。按子树划分操作和顶点。对于每个子树，对源自子树的操作重复此累积摘要，但使系数为正而不是负。通过将子树的摘要与 v 的摘要放在一起，我们可以确定源自子树外部的减少操作的影响。最后，我们对每个子树进行递归。

现在，对于每个顶点 w，我们使用二进制搜索计算死亡时间。影响 w 的减少操作在以前面描述的方式计算的对数摘要中给出，因此一个顶点的总成本是 log^2。

作为提问者，听起来好像您知道下一部分是如何进行的，但为了完整起见，我将对其进行描述。进行前序遍历以将新标签分配给顶点，并为每个顶点计算包含其子树的标签间隔。初始化 Fenwick 树，将每个顶点映射到一个(活)或零(死)，最初是一个。将死亡时间和查询放在优先队列中。要处理死亡，请将该顶点的值减一。要处理查询，请对子树区间中的顶点值求和。