Persistent Segment Tree

It’d be really nice if someone can take up a problem as example and explain the approach of solving it using a persistent segment tree.There are 1-2 problems on codechef but editorials of those problems explain very little about the persistence part.
e.g. for example to solve this problem(or any other problem) using persistent segment tree

what will be the approach i.e. if someone can explain how we are building n segment trees and after that how we are querying,it’ll be very helpful.

1 Like

A persistent data structure is one where you can answer queries for different versions of the data structure. Meaning you can shift between the newly updated and old versions.

For a persistent segment tree, each update costs you log(n) operations, because an update query of any range will effect at most log(n) nodes. This allows us to update the tree to a new version efficiently.

Here is a video tutorial on the exact problem you are talking about.
An MIT lecture talks about persistent data structures in general.

Happy Coding!


@gkcs I really like your videos. You’re doing a great job.

Can you please do a video on Mo’s Algorithm ( and if possible with updates on it ) ?

I saw your video on sqrt-decomposition, it was crystal clear and intuitive ( Also the implementation part really helps ).


You can follow this awesome link

1 Like

Mo’s algorithm sounds good. I should be able to make one soon.
Thanks for the suggestion and feedback!

If you will be making, then please add the update part too. Except this ( ) and this ( ) I didn’t find any other resource on Mo’s with Updates.
Will be looking forward to your video :slight_smile:

1 Like