Monday, September 26, 2016

Segment Tree For Min Query Java


public class SegmentTreeMin {
private static int[] arr = {1,9,2,3,5,8,90,1,2,88};
private static Node[] stArr;

private static int query(int root,int low,int high) {
//System.out.println("query");
if(root>=stArr.length) return -1;
Node n = stArr[root];

//no intesection
if(low > n.r || high < n.l) {
return -1;
}
//n is contained between low & high
if(n.l >= low && n.r <= high) {
return n.val;
}
//low <= n.r && high >= n.l
int l_ind = query(root*2+1,low,high);
int r_ind = query(root*2+2,low,high);
int min = Integer.MAX_VALUE;
int min_index = -1;
if(l_ind > -1) {min = arr[l_ind];min_index = l_ind;}
if(r_ind > -1 && arr[r_ind] < min) {min = arr[r_ind];min_index = r_ind;}
return min_index;
}
private static void construct(int root,int low,int high) {
if(high<low) return;
if(root>=stArr.length) return;
Node n = new Node(low,high);
stArr[root] = n;
if(low==high) { n.val = low; return;}
int mid = low + (high-low)/2;
construct(2*root+1,low,mid);
construct(2*root+2,mid+1,high);
Node left = stArr[2*root+1];
Node right = stArr[2*root+2];
int lval  = left!=null?arr[left.val]:Integer.MAX_VALUE;
int rval  = right!=null?arr[right.val]:Integer.MAX_VALUE;
if(lval<rval) n.val = left.val; else n.val = right.val;
}
public static void main(String[] args) {
int stlen = (int) Math.ceil(Math.log(arr.length*1l)/Math.log(2l)) + 1;
stArr = new Node[(int)( Math.pow(2, stlen) - 1)];
construct(0,0, arr.length-1);
int min_index = query(0,5,7);
int minVal = min_index > -1?arr[min_index]:-1;
System.out.println(minVal);
/*for(int i=0;i<stArr.length;i++) {
Node n = stArr[i];
if(n!=null) {
System.out.println(i+" "+n.l+" "+n.r+" "+n.val);
}
}*/
}
}

class Node {
int l;
int r;
int val;
public Node(int l,int r) {
this.l = l;
this.r = r;
}
}

No comments:

Blog Archive