Untitled

sakshamjain08
plain_text
7 days ago
1.6 kB
0
Indexable
Never
```//  Segment Tree Max in an interval query.
public class Main {
public static void main(String[] args) {
int []arr = {8,7,4,2,5,3,1,10};

SegmentTree s = new SegmentTree(arr);

System.out.println(s.query(0,7));
System.out.println(s.query(0,3));
System.out.println(s.query(2,5));
System.out.println(s.query(1,6));
}
}

class SegmentTree{
int []tree;
int []arr;

public SegmentTree(int []arr){
this.arr = arr;
this.tree = new int[4*arr.length];
build(0,0,arr.length-1);
}

public void build(int idx, int l, int h){

if(l == h){
this.tree[idx] = this.arr[l];
return;
}

int mid = l + (h-l)/2;
build(2*idx + 1, l,mid);
build(2*idx + 2, mid+1,h);
this.tree[idx] = Math.max(this.tree[2*idx+1], this.tree[2*idx+2]);

}

public int query(int l, int r){
return query(0,0,arr.length-1, l, r);
}

private int query(int idx, int start, int end, int l, int r){

// contains
if(l <= start && end <= r){
return this.tree[idx];
}

// non overlapping
if(end < l || r < start){
return Integer.MIN_VALUE;
}

// overlapping

int mid = start + (end - start)/2;
int left = query(2*idx+1, start, mid, l,r);
int right = query(2*idx+2, mid+1, end, l, r);

return Math.max(left,right);

}

}```