Skip to content

Latest commit

 

History

History
 
 

Segment_Tree_RMQ

Segment Tree

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.

Explanation

Consider an array A of size N and a corresponding Segment Tree T:

  1. The root of T will represent the whole array A[0 : N-1].
  2. Each leaf in the Segment Tree T will represent a single element A[i] such that 0 <= i < N.
  3. 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:

Pic01

Pic02

Algorithm

Query for minimum value of given range

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) )
}

Pseudocode

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;
}

Example

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.

Pic03

Time Complexity

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).

Implementation

-C Code

-C++ Code

-Python Code

-Dart Code

-Java Code

References

Images source:

  1. https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/
  2. https://www.topcoder.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/

Websites:

  1. https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/
  2. https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
  3. https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
  4. https://www.srcmake.com/home/segment-tree