Implicit Segment tree/ Dynamic Segment tree

Implicit Segment tree , is similar to static segment tree , Here we create nodes only when required, that’s why it is also known as dynamic segment tree.

Example : Implicit segment tree with addition on the interval
and getting the value at some index.

Also it works on large interval let say [1 - 1000000000]

( In that case , initial Array is empty, as we can’t take large Array as input , due to constraint on time and space )

Update and Query : O(LogN)

Space : O(NLogN)

Code : http://ideone.com/Oe6jZ2 ( Simple as much as static ST )

To learn more amazing ds with implementation

Visit the page : https://www.facebook.com/programmingcompetitive/

3 Likes