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.
Can u give link to quora page.
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.
3 Likes