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 : ( Simple as much as static ST )

To learn more amazing ds with implementation

Visit the page :