Persistent Segment Tree

#1

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
http://www.spoj.com/problems/MKTHNUM/

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.

4 Likes
#2
1 Like
#3

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!

2 Likes
#4

You can follow this awesome link

1 Like
#5

@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 ).

Thanks.

#6

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

#7

If you will be making, then please add the update part too. Except this ( http://codeforces.com/blog/entry/44711?#comment-292040 ) and this ( https://www.hackerearth.com/problem/algorithm/tree-and-coprime-queries/editorial/ ) I didn’t find any other resource on Mo’s with Updates.
Will be looking forward to your video :slight_smile:

1 Like