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

×

Persistent Segment Tree

4
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.

asked 27 Jan '14, 02:36

orchidmajumder's gravatar image

3★orchidmajumder
3584815
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!

link

answered 26 Feb '17, 11:12

gkcs's gravatar image

4★gkcs
2.6k11128
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 ).

Thanks.

(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★
1

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

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

answered 26 Feb '17, 12:37

inovation123's gravatar image

3★inovation123
4537
accept rate: 10%

edited 26 Feb '17, 12:38

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,755
×208
×116

question asked: 27 Jan '14, 02:36

question was seen: 11,564 times

last updated: 27 Feb '17, 01:42