data-structures - 如何设计此功能以在对数时间内工作？

Question

我有一个展开树，我已经实现了 range_sum(left,right)，它将树中的所有元素添加到从左到右的范围内，并且它在对数时间内工作，无论如何我可以制作一个函数 range_up(left,right ,delta) 将 delta 添加到从左到右范围内的每个元素并在对数时间内工作？

Answer 1

您可以使用延迟更新来做到这一点。这个想法是在每个节点中放置一个字段到每个节点中，上面写着“这个节点，以及它下面的所有节点，都隐式地将 Δ 添加到它们的所有值中。” 在展开逻辑中执行旋转时，您可以向下推此增量值。

要将数量添加到范围内的所有值，首先要搜索范围内节点的最低共同祖先（这是范围的一端在一个方向而另一端在另一个方向的节点）。更新那里的 delta 字段，这会将 delta 添加到该子树中的所有节点。这包括您想要的所有节点，以及一些您不想要的节点。从那里，对范围的最小/最大元素进行一对前驱/后继搜索。当您进行这些搜索时，您会从 LCA 向下移动到两个叶子，更新您在范围之外遇到的节点的 delta 字段以撤消您在 LCA 中添加的 delta。（更准确地说，当您向下走时，每次超出范围时，在节点处添加 -Δ 以撤消对 delta 的应用，当您回到范围内时，将 Δ 添加到节点以进行校正。）

这会执行两次从根到叶的遍历，并且如果您在最后都展开，则更新的摊销成本为 O(log n)。