我正在考虑这个问题，并且在尝试执行此操作时遇到了很多错误。可能吗？
问问题
421 次
1 回答
0
我相信您在问是否可以进行以下更新：给定更新 ABC，您希望将 C 添加到从 A 到 B 的所有元素。
问题是对分段树进行更新通常需要 O(N * logN) 时间，因为 N 是最大元素数。但是，实现分段树的关键思想是您希望假设范围查询，并且通常您对所有 O(N^2) 范围不感兴趣，而是对其中的一小部分感兴趣。
您可以使用延迟传播来增强范围更新，这通常意味着您进行更新，但您不会更新段树中的所有节点 -> 您更新到某个点，但您不会继续沿着树向下继续它不需要。
假设您已将所有内容更新到负责范围 [10; 30] 例如。稍后，您在 [20;40] 上执行“获取信息”查询。显然，您将不得不访问节点 K，但您对整个范围不感兴趣，而是对范围 [20;30] 感兴趣，这实际上是它的右孩子。
您要做的是将节点 K 的更新“推送”到其左孩子，然后是其右孩子，并根据需要继续。
一般来说，这意味着在进行更新时，您只会进行更新，直到您找到适合您更新时间间隔的节点，但不会继续更新。这会产生 O(logN) 时间。
然后，在查询时，当您到达一个您知道已为其保存了一些更新以供以后使用的节点时，您继续沿树传播更新。这也会产生 O(logN) 时间。
一些好材料：分段树上的延迟传播
于 2015-04-18T20:24:45.803 回答