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 (Balkan, not Baltic) 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 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! :)