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

×

dynamic segment tree of dynamic BSTs

While reading an article on Quora, I came across this data structure "dynamic segment tree of dynamic BSTs". I know and can code segment trees, but what is this dynamic segment tree of dynamic BSTs. Google won't give enough info on this one. Can anyone tell me what is this and when we use this?
Also, it would be great if you know any problem which uses this.
No luck so far.

asked 16 Feb '15, 01:41

mayankb_03's gravatar image

1★mayankb_03
115621
accept rate: 16%

edited 22 Feb '15, 04:03

Can u give link to quora page.

(16 Feb '15, 01:42) utkarsh134★

I googled dynamic segment tree and found this blog on codeforces.
Here i read this comment by a user which explains the main idea of dynamic segment trees.

" Main idea: in dynamic segment tree we create a node only when we need in it.
Example: "Monkey and apples" from IZhO 2012 — Given an array of size 109 and 2 types of queries — assign 1 to segment [L, R] and get sum on segment [L, R]. Tree: We can create struct with four parameters (sum, assign_value, left_node, right_node).
Update: Apply the main idea. Assume that you stand in node 1 (segment [1, 109]) and you need to assign 1 to segment that means you need to go to your left child in tree. If your current node haven't got left (or right, doesn't matter) child we can just create it, can't we? You can do it easily — just keep counter.
Get sum: Again assume that you need to find sum on segment and you are currently in node 1. If your current node haven't got left child that means that you never updated this segment so it have zero sum else you can just return it's sum. "

Also i found this code, which will help you implementing it.

link

answered 31 Mar '16, 10:09

hm_98's gravatar image

6★hm_98
2806
accept rate: 0%

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,727
×154

question asked: 16 Feb '15, 01:41

question was seen: 3,174 times

last updated: 31 Mar '16, 10:09