Segment Tree is a basically a binary tree used for storing the intervals or segments. Each node in the Segment Tree represents an interval.
Segment Tree is used in cases where there are multiple range queries on array and modifications of elements of the same array. For example, finding the sum of all the elements in an array from indices L to R, or finding the minimum (famously known as Range Minumum Query problem) of all the elements in an array from indices L to R.
Consider an array A of size N and a corresponding Segment Tree T:
- The root of T will represent the whole array A[0 : N-1].
- Each leaf in the Segment Tree T will represent a single element A[i] such that 0 <= i < N.
- The internal nodes in the Segment Tree T represents the union of elementary intervals A[i : j] where 0<=i<j<N.
- The root of the Segment Tree represents the whole array A[0 : N-1].
- Then it is broken down into two half intervals or segments and the two children of the root in turn represent the A[0 : (N - 1)/2] and A[(N-1)/2 +1 : (N-1)].
- So in each step, the segment is divided into half and the two children represent those two halves. So the height of the segment tree will be log2N.
- There are N leaves representing the elements of the array. The number of internal nodes is N - 1. So, a total number of nodes are 2 * N - 1.
The Segment Tree of array A of size 7 will look like this:
Once the tree is constructed, how to do range minimum query using the constructed segment tree. Following is the algorithm to get the minimum.
// qs --> query start index, qe --> query end index
int RMQ(node, qs, qe)
{
if range of node is within qs and qe
return value in node
else if range of node is completely outside qs and qe
return ZERO
else
return min( RMQ(node's left child, qs, qe), RMQ(node's right child, qs, qe) )
}
After we've built a tree, we want to be able to search the tree for its values. (Which, in this case, is the minimum value between indices L and R.)
Similar to the technique we used before, we recursively search the tree, starting from the root, and if a node is within the range [L, R], then we check it's value as a valid minimum of the range.
function RecursivelySearchForMin(L, R, nodeIndex, nodeStartIndex, nodeEndIndex)
{
/*
If this node's range is anywhere outside of [L, R]
then don't use it's value. Just return some
really big number (which wouldn't be taken as the minimum).
*/
if(nodeEndIndex < L || R < nodeStartIndex)
{
return reallyBigNumber;
}
/*
If this node is completely within [L, R],
then return it as the min value.
*/
if(L <= nodeStartIndex && nodeEndIndex <= R)
{
return stArray[nodeIndex];
}
/*
Otherwise this node is partially within [L, R].
(Recursively) check this node's children and return the min of those two.
*/
middleIndex = nodeStartIndex + ((nodeEndIndex - nodeStartIndex) / 2);
leftChildNodeIndex = 2 * nodeIndex;
rightChildNodeIndex = 2 * nodeIndex + 1;
leftChildMin = RecursivelySearchForMin(L, R, leftChildNodeIndex, nodeStartIndex, middleIndex);
rightChildMin = RecursivelySearchForMin(L, R, rightChildNodeIndex, middleIndex + 1, nodeEndIndex);
minOfThisNode = min(leftChildMin, rightChildMin);
return minOfThisNode;
}
// Find the minimum value between indices L and R.
function FindMin(L, R)
{
// Recursively search the tree, starting from the root (node 0).
min = RecursivelySearchForMin(L, R, 0, 0, origArrayLength - 1);
return min;
}
Given an array A[1 … n] of n objects taken from a well-ordered set(such as numbers), returns the position of the minimal element in the specified sub-array A[l … r], (r<=n).
When A = [2,4,3,1,6,7,8,9,1,7], then the answer to the range minimum query for the sub-array A[2 … 7] = [3,1,6,7,8,9] is 3, as A[3] = 1.
Time Complexity for tree construction is O(n). There are total 2N - 1 nodes, and value of every node is calculated only once in tree construction.
Time complexity to query is O(Log N). To query a range minimum, at worst, we'll have to go down the height of the tree twice, once for the left subtree, and one for the right subtree. We process at most two nodes at every level and number of levels is O(Log N).