Dynamic Segment Trees

Revision en2, by P_Nyagolov, 2015-07-05 01:45:24

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

Tags dynamic trees, segment trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English P_Nyagolov 2015-07-05 20:35:19 597
en2 English P_Nyagolov 2015-07-05 01:45:24 23
en1 English P_Nyagolov 2015-07-05 01:44:02 805 Initial revision (published)