Introduction to Segment Trees
A segment tree is an efficient data structure that’s commonly utilized for range queries. It’s a static binary tree with a height-balanced structure. The nodes of a segment tree correspond to various intervals and can be supplemented with relevant data for those intervals. With segment/range data stored, the segment tree offers a log N time complexity for range queries as well as modification in the input data set.
A segment tree is a complete binary tree with 0 or 2 children at each node and all levels filled except the final. The segment tree’s leaf nodes will hold the single items of the input array, while all other internal nodes will represent a range.
The root of segment Tree will represent the whole range arr[0…n-1].
Each leaf node of segment Tree will holds a single element a[i] where 0 ≤ i < N
The internal nodes of the segment Tree holds a range operation arr[i...j] such that 0 ≤ i < j < N
A segment tree of array length 8 will look like this:
Segment Tree Implementation
Similar to Heap, Segment trees can also be implemented using an array.
We begin at the root of the segment tree with the range arr[0…n-1] and divide the current range into two halves until it becomes a range of length 1 and then with a bottom-up approach we start combining the segments storing the sum in the relevant segment tree node for each segment.
The size of the array used to hold the segment tree is 2n-1, where n is no of nodes in the input array. If n is not a power of 2, the size is 2m-1, where m is the next power of 2 greater than n.
Range queries:
We need to iterate over a maximum of log N items in the segment tree to discover the results of range queries. Starting from the root, we descend recursively until we reach the exact range segment or a segment lying under the actual range, we find out all such segments and then aggregate all of them to get the result.
Updating elements
We must adjust the segment tree in order to change the segment tree elements as arr[i] = newValue. The exact element to edit is undoubtedly located in one of the segments of the tree, requiring us to modify a maximum of log(N) nodes. Starting from the root, we will descend recursively to the lower segments until we find the leaf node with the index, and then update all segment ranges up to the root using a bottom-up strategy.
Closing Thoughts:
When you have a search-heavy application that runs a lot of particular range queries on a data source, the Segment Tree is an excellent data structure to use (e.g., sum, min, and max queries). The segment tree has wide applications in computational geometry, geographic information systems, and machine learning.