Segment trees

December 10th, 2020 17:58

Recently I read about a data structure which I found to be the most interesting data structure from the point of view of generic problem solving. As the title of this post indicates, this data structure is segment tree.

A segment tree is as the name says a tree, whose each leaf can be made to indicate corresponding data items in an array, and each non leaf node can be a processed value. This processed value can be things such as minimum of leaf nodes, their sum, their GCD, LCM etc.

What the segment tree allows is to allow something like finding the sum of all values between index i and j in an array A[N] in O(logN) time. We can find the sum between these i and j indices in O(1) time if we use a prefix sum array, but then updating even 1 value in the original array would need recalculation of the entire prefix sum, which would be O(N). Using segment tree, we can do both the updates and query in O(logN) time, which is great.

Also, the implementation of segment tree is fairly simple and straight forward.

There are lots of interesting applications of it. For details, I suggest you look up this write up on segment tree