Segment Tree | Set 2 (Range Minimum Query) | GeeksforGeeks

We have an array arr[0 . . . n-1]. We should be able to efficiently find the minimum value from index qs (query start) to qe (query end) where 0 <= qs <= qe <= n-1. The array is static (elements are not deleted and inserted during the series of queries).
With segment tree, preprocessing time is O(n) and time to for range minimum query is O(Logn). The extra space required is O(n) to store the segment tree.

Representation of Segment trees
1. Leaf Nodes are the elements of the input array.
2. Each internal node represents minimum of all leaves under it.

An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2*i+1, right child at 2*i+2 and the parent is at .

Java Implementation

public class RMQTree {

    int[] data;

    int[] tree;

     

    int nextPowerOf2( int n ){

        int p = 1;

        for( ; p < n; p <<= 1 );

        return p;

    }

     

    void init( int root, int f, int t ){

        if( f == t ){

            tree[root] = f; 

        }

        else{

            int m = (f+t)/2, l = left(root), r = right(root);

            init( l, f, m );

            init( r, m+1, t );

            tree[root] = ( data[tree[l]] < data[tree[r]] ) ? tree[l] : tree[r];

        }

    }

    RMQTree( int[] a ){

        data = a;

        int n = a.length;

        int p = nextPowerOf2( n );

        tree = new int[2*p-1];

        init( 0, 0, n-1 );

    }

    int parent( int i ){

        return (i-1)/2;

    }

    int left( int i ){

        return 2*i+1;

    }

    int right( int i ){

        return 2*i+2;

    }

 

    int minimum( int root, int low, int high, int f, int t ){

        // return

        //  the index of the minimal value of the array within the range a[f, ..., t],

        //  provided the portion of the array within the range a[low,...,high]

        if( t < low || high < f )

            return -1;

        if( f <= low && high <= t )

            return tree[root];

        int l = left(root);

        int r = right(root);

        int m = (low+high)/2;

        int l_min = minimum(l, low, m, f, t );

        int r_min = minimum(r, m+1, high, f, t );

        if( l_min==-1 )return r_min;

        if( r_min==-1 )return l_min;

        return data[l_min] < data[r_min] ? l_min : r_min;

    }

    int minimum( int f, int t ){

        return minimum( 0, 0, data.length-1, f, t );

    }

}

Read full article from Segment Tree | Set 2 (Range Minimum Query) | GeeksforGeeks