问题标签 [lazy-propagation]

最近遇到了一个叫做重力树的问题 ，我自己解决不了，所以我查看了社论. 作者的解决方案是对顶点进行一次 dfs 并形成一个分段树。其中每个节点包含从顶点到中心的距离。然后他提到了第二个 dfs（我不知道那在做什么。我尝试打印他的数据结构，但它们完全没有意义。不知道他实际上在做什么）。他写的语言有点太难掌握了。我知道什么是段树、dfs、惰性传播。但我无法围绕这个解决方案。不知道解决方案让我非常焦虑，我无法专注于其他事情。如果有人能给出更清晰的解释，那就太好了。以至于其他糊涂的人也受益匪浅。提前致谢 ：）

问题制定者很固执。

考虑这个问题。在这个分段树解决方案中，我们正在更新给定范围内的树的所有节点。是否可以对这个问题应用惰性传播？

编辑：考虑在每个更新操作arr[i] = (1-(1-arr[i])*a)中， whereL<=i<=R和a是一个常数。

我正在阅读 GFG 上的惰性传播，它说要进行范围更新

例如，考虑上图中值为 27 的节点，该节点存储索引从 3 到 5 的值的总和。如果我们的更新查询是针对范围 2 到 5，那么我们需要更新该节点和该节点的所有后代 Segment树形图

我不明白范围是否为 2 到 5 为什么我们应该只更新 27 而不是其他在其范围内也包含 index = 2 的节点

链接到文章

假设有两个序列 A:a1,a2,...,an 和 B:b1,b2,...bn ，我们需要两个操作：

1.sum(i,j):计算ai,a(i+1),...,aj的和

2.range_add(i,j):range 修改[i,j]中的序列A，其中ai=ai+b1,a(i+1)=a(i+1)+b2,...,aj= aj+b(j-i+1)

是否可以进行 O(log n) 时间的操作？

一个简单的惰性传播树似乎无法解决问题，如果您将区间的总和存储在节点中，并使用序列 B 中的第一个加数来标记一个惰性修改的节点，因为当对一个节点进行修改时已经被标记了，你不能简单地把新的变化和之前的变化结合起来，你必须把之前的标签往下推，如果他们的孩子也已经被标记了，那么就需要更多的推送，导致总时间复杂度 O(n)。

也许我们可以将所有标签存储在一个数组中，并将当前节点的标签推到其子标签数组的后面，我想知道这个算法是 O(log n) 还是 O(n)？（应该是 O(n)，因为我在 codeforces 中的提交失败了，所以我实际上想知道如何计算时间复杂度）

https://codeforces.com/contest/446/problem/C 这就是我的问题所在。