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 12 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. asked 27 Jan '14, 02:36

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! answered 26 Feb '17, 11:12
@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 sqrtdecomposition, it was crystal clear and intuitive ( Also the implementation part really helps ). Thanks.
(26 Feb '17, 12:32)
@nikhil_chandak Mo's algorithm sounds good. I should be able to make one soon. Thanks for the suggestion and feedback!
(26 Feb '17, 12:53)
1
If you will be making, then please add the update part too. Except this ( http://codeforces.com/blog/entry/44711?#comment292040 ) and this ( https://www.hackerearth.com/problem/algorithm/treeandcoprimequeries/editorial/ ) I didn't find any other resource on Mo's with Updates. Will be looking forward to your video :)
(27 Feb '17, 01:42)

answered 21 May '15, 18:22

You can follow this awesome link http://www.geeksforgeeks.org/persistentsegmenttreeset1introduction/ answered 26 Feb '17, 12:37
