I'm learning sustainable data structures now. And I've got the main idea of it, that is to share some common data with the old versions. Now I want to implement lazy propagation on sustainable segment tree and I've got some problems.
It is no difference when I put a lazy tag on a sustainable segment tree or a normal tree. But when I want to push down the lazy tag to its children, I can't directly modify the children because old versions use the same memory and it will get WA on queries to the old versions later.
So what should I do in such cases? And I think of dynamic allocating new space for these shared part of the tree. Is it a good solution to the problem? And how to connect its subtrees so that will not use too much additional space(it should be at most O(lgn) memory allocated per action)?
For example I put a lazy tag on segment [1,8] before and now I want to push down to [1,4] && [5,8] but what will be these new nodes' children? Apparantly keep allocating is not a correct way because that may use O(n) space.
I think you can allocate copies of these two children, but not the whole subtree. The new children can link to the original children of children as their children.
I think that the easiest way to implement everything is to use copy-on-write, i.e. whenever you need to modify data in a node of the segment tree, just create a copy of it and modify the data in that copy instead (when creating the copy you copy the data in the node and the "pointers" to its children). Moreover, if you created a copy of a node, you should also have created copies of all of its ancestors. This way you would create O(log(N)) new nodes for every update operation (and you would also have a new version for every update operation). A simpler explanation is that for each update operation, every time you need to visit a node you instead first create a copy of the node and then visit that copy.
I usually use this approach when I need to implement persistent segment trees. If you know in advance an upper bound on the total number of nodes you may have, then you can allocate all of them from the very beginning (e.g. in a large array of nodes).
Thanks! I know I should copy all the ancestors because we need an entry for all versions. Copying only its children is really a nice way. I didn't think of that before.. It helps me a lot :D
The easiest way to get this done is to create a wholly new copy of the node on each update query and link the new parent to it (Note that the parent must've had a new copy created as the update query descends down the tree)
The total memory complexity of this is QLogN where Q is the number of update queries you will have, each query will result in AT MOST Log(n) new nodes created.
Yep, this is exactly what I said (in way too many words :) )
Aha now I see; sorry for reposting what you said :(