Untitled

//  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);

      }

  }