Segment Tree

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 looping over the array and diving in half which takes linear amount of time, then while recursing up while combing the sorted list in liniear amount of time. So we can use this information to analyze mergesort runtime. If we see the width of the array we get at the end of splitting the array , we get the width as n so, that’s O(n) and the height of the array is log n because we are splitting the array in half each time and log of something basically means how many time we can diving that in half. Now if we combine both width and height we get the area a nlogn that means the complexity of merge sort is O(nlog n).

Now that we know how merge sort works the question is- how can we turn this into data structure? For that we’ll consider each array of the merge sort as different nodes and use the nodes to form a tree. So, I am taking the sequence of the recursion and turning it into data structure. The tree will look like below: