c++ - 清除范围（将范围设置为零）惰性段树修改

Question

我想在下面的链接中将一个函数添加到延迟传播实现中，将范围设置为 0。目前有一个 update_tree 函数可以增加一个范围，但我不知道如何修改它以便它将在 O(log(N)) 时间内将范围懒惰地设置为零。

http://se7so.blogspot.com.au/2012/12/segment-trees-and-lazy-propagation.html

我正在考虑在每个节点上使用“延迟清除”标志，但我怎么知道先清除然后延迟添加或延迟添加然后清除（这会很清楚）？

Answer 1

在每个包含要处理的操作的节点上使用队列而不是标志，只要您使用 FIFO 数据结构，您就可以确保它们以正确的顺序完成。除非我错过了这个问题的重点。