清除範圍（設置範圍爲零）延遲段樹修改

我想在下面的鏈接中的延遲傳播實現中添加一個函數，將範圍設置爲0.目前有一個update_tree函數，範圍，但我不知道如何修改它，以便在O（log（N））時間內將範圍設置爲零。清除範圍（設置範圍爲零）延遲段樹修改

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

我想用「懶惰明確」標誌在每個節點的，但我怎麼會知道，清除第一則懶添加或懶加載，然後清除（這將是剛剛清）？

2013-02-16 William Rookwood

只要您使用FIFO數據結構，您可以確保它們按正確的順序完成，在每個包含要處理操作的節點上使用隊列而不是標誌。除非我錯過了這個問題的觀點。

2013-02-16 22:45:57 Justin

那麼你是在暗示，而不是懶惰的[MAX]數組，我用一個隊列 lazy [MAX]替換它，所以一個隊列映射到每個節點？然後當我傳播一個節點時，我從隊列中彈出操作並將它們推送到子節點隊列中？隊列永遠不會超過2個項目是正確的？ – 2013-02-16 23:04:11

是的，但隊列永遠不會超過2個項目是一個實現細節。我已經實現了懶惰段樹，其中所有修改（添加，清除）都簡單地推送到每個受影響節點的隊列中。一旦執行查詢，就會處理每個節點（涉及查詢）隊列中的所有內容。從本質上講，以降低查詢爲代價可以更快地進行修改。 – Justin 2013-02-16 23:08:11

@WilliamRookwood看到我上面的評論。 – Justin 2013-02-17 02:19:09

清除範圍（設置範圍爲零）延遲段樹修改

回答

相關問題