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 : Oe6jZ2 - Online C++0x Compiler & Debugging Tool - Ideone.com ( Simple as much as static ST )
To learn more amazing ds with implementation
Visit the page : Redirecting...