dx24816's blog

By dx24816, history, 9 months ago, In English,

Hello,

Recently, I've been learning about the persistent segment tree. However, is there a way to get a persistent segment tree with range updates, and not just point updates? If so, can someone direct me to a clean and easy implementation in C++? Thanks!

-dx24816

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +41 Vote: I do not like it

If you're talking about persistent lazy propagation, it's obviously possible. Once you understand the concept, you'll see that it's not really different. You'd just have to use more memory and the implementation would be a bit harder.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is the explanation with some code: Persistent Lazy Propagation