Segment Tree

Shaila Nasrin
7 min readMar 17, 2019

Segment tree is basically taking the recursion pattern of merge sort and turning it into data structure. So, before we start with segment tree we have to know how merge sort works. If we see the diagram below:

So, what we are doing here is- we are recursing down the array by diving it in half and then we are recursing back up and merging the sorted array. On each level while recursing down it take linear amount of time because we are…

--

--