segment tree correct but query output is not

Question

I tried to implement segment tree algorithm for finding range minimum query in Java. Here is my complete java code. It builds the segment tree from an array. and then prints the minimum element in every range. the problem is, tree is correct (as far as I know), but the output is always the least element of whole array. :-| kindly point out where I am going wrong.

public class Solution {

static int arr[] = {-1, 2, 4, 0};
static int st[];

public static void main(String[] args) {

    st = new int [ 2 * arr.length-1];

    buildTree(0, 0, arr.length-1);

    System.out.print("original array: ");
    showArray(arr);

    System.out.print("segment tree: ");
    // shows segment tree
    showArray(st);

    System.out.println("\nqueries: \n");

    // prints minimum in every range
    for(int i=0; i<arr.length; i++) {
        for(int j=i+1; j<arr.length; j++) 
            System.out.println(i+":"+j+" -> "+search(i, j));
    }

}

// builds segment tree
static void buildTree(int pos, int left, int right) {

    if(left == right) {
        st[pos] = arr[left];
        return;
    }

    int mid = (left + right) / 2;

    buildTree(left(pos), left, mid);
    buildTree(right(pos), mid+1, right);

    int p1 = left(pos);
    int p2 = right(pos);

    st[pos] = (st[p1] > st[p2]) ? st[p2] : st[p1];
}

// left child
static int left(int pos) {
    return pos * 2 + 1;
}

// right child
static int right(int pos) {
    return pos * 2  + 2;
}

static int search(int left, int right) {

     return rmq(0, 0, st.length, left, right);
}

// range minimum query function
static int rmq(int pos, int left, int right, int qleft, int qright) {

    if((qleft > right) && (qright < left))
        return Integer.MAX_VALUE;

    if((qleft <= left) || (qright >= right))
        return st[pos];

    int mid = (left + right) / 2;

    int l = rmq(left(pos), left, mid, qleft, qright);
    int r = rmq(right(pos), mid + 1, right, qleft, qright);

    return (l > r) ? r : l;
}

// show segment tree
static void showArray(int arr[]) {

    for(Integer x : arr)
        System.out.print(x+" ");
    System.out.println();
 }
}

Answer 1

You have to make following changes in your code.

First of all size of array used for storing data in segmentree datastructure should be 4 times of size of given array. Here is why?

st = new int [ 4 * arr.length - 1];

Next in search function, you third parameter for rmq must be arr.length - 1.

static int search(int left, int right) {
     return rmq(0, 0, arr.length - 1, left, right);
}

And finally, you have to correct base cases and arguments in child calls in rmq function as follows:

static int rmq(int pos, int left, int right, int qleft, int qright) {

    if((qleft > right) || (qright < left))
        return Integer.MAX_VALUE;

    if((qleft <= left) && (qright >= right))
        return st[pos];

    int mid = (left + right) / 2;

    int l = rmq(left(pos), left, mid, qleft, Math.min(qright, mid) );
    int r = rmq(right(pos), mid + 1, right, Math.max(mid + 1, qleft), qright);

    return (l > r) ? r : l;
}

Hope this helps.