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/