P_Nyagolov's blog

Dynamic Segment Trees
By P_Nyagolov, history, 9 years ago, In English

Hello everybody,

Last year I read that dynamic trees exist, that is trees in which we create only the nodes we need since there can be a lot (say we have indices 1,...,10^9). I thought it's cool and wanted to know more about it. I googled a few times "Dynamic BIT", "Dynamic trees" or something like that but I found nothing...

Recently I participated in BOI 2015 and there was a problem that required a segment tree for 60 points and dynamic segment tree or AVL Tree which I can't code for full score so I wasn't able to get more than 60 on it. Now, I tried googling "Dynamic Segment Tree" but found nothing...

Can somebody please explain how dynamic segment trees work and give me an implementation, I would appreciate your help!

Thanks in advance! :)

UPD: Thanks everybody for the help, I understood it! So basically, we initially have the root only which stores the whole interval ([1;10^9] for example). Then the update/query goes exactly like in the normal segment tree but if we don't have a child of some node but we need it, we just create it and go on. I implemented Horrible Queries from SPOJ (I know that a normal segment tree is enough, but I wanted to test it). Here is my accepted code, it might be helpful for somebody who has problems with this structure — http://ideone.com/hdI5aX.

  • Vote: I like it
  • +23
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

My implementation

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

You can use coordinates compression technique. For example if we have 105 numbers each less than 109 you can sort them and give every unique number an index, so you will have up to 105 element and you can use segment tree easily. I've seen an implementation to dynamic segment trees using pointers and stuff but I prefer this technique to not complicate things..

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Unfortunately, you could not use this technique as the task in question was interactive, so online solution was required.

    → Reply
»
9 years ago, # |
← Rev. 10   Vote: I like it +19 Vote: I do not like it

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.

Links: Problem (Day 2, F), tests, my code, jury's code, participants' codes.

P.S Sorry for my poor English.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you very much for your explanation, the jury solution helped me too! :)

    → Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You can find my implmentation in ADJA's github repo https://github.com/ADJA/algos/blob/master/DataStructures/ImplicitSegmentTree.cpp.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me why am i wrong?

http://ideone.com/BxPXmD

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    NO! What is wrong with you? This is an year old post!

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

There is another idea for that. It is more easy to code but every query will have O(lg2).

Use map for saving segment tree (or BIT(fenwick tree) ). like this : 18066766.

You can use unordered_map too.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, I have always used that for dynamic fenwick but it never came to my mind to do it for segment tree, thanks. BTW, is there a way to make dynamic fenwick tree that works in log instead of log^2 (excluding unordered map because such tree didn't perform well if I remember correctly)?

    → Reply