You are not logged in. Please login at to post your questions!


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.

asked 27 Jan '14, 02:36

orchidmajumder's gravatar image

accept rate: 0%

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's gravatar image

accept rate: 9%

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


(26 Feb '17, 12:32) nikhil_chandak5★

@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) gkcs4★

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 :)

(27 Feb '17, 01:42) nikhil_chandak5★

answered 26 Feb '17, 12:37

inovation123's gravatar image

accept rate: 10%

edited 26 Feb '17, 12:38

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 27 Jan '14, 02:36

question was seen: 11,564 times

last updated: 27 Feb '17, 01:42