SegmentTree.java

import java.util.*;
import java.lang.*;
import java.io.*;
class SegmentTree
{
    int st[];
    Segment(int []arr, int n)
    {
        int x = (int) Math.ceil((Math.log(n)/Math.log(2)));
        int max_size = 2 *(int) (Math.pow(2,x) - 1);
        st = new int[max_size];
        
        constSegmentUtil(arr,0,n-1,0);
    }
    
    int constSegmentUtil(int []arr, int ss,int se,int si)
    {
        if(ss == se)
        {
          st[si] = arr[ss];
          return arr[ss];
        }
        int mid = getMid(ss,se);
        st[si] = max(constSegmentUtil(arr,ss,mid,2*si+1),constSegmentUtil(arr,mid+1,se,2*si+2));
        return st[si];
    }
    
    int getMid(int s,int e)
    {
		  return s + (e - s)/2;
    }
    
    int max(int a,int b)
    {
      if(a > b)
      {
        return a;
      }
      else{
        return b;
      }
    }
    
    void print(){
        for (int i=0;i<st.length;i++ )
        {
            System.out.print(st[i]);
        }
    }
    
    int getMaxUtil(int ss,int se,int qs,int qe,int si)
    {
        if(qs<=ss && qe>=se)
        {
            return st[si];
        }
        
        if(se<qs || ss>qe)
        {
            return 0;
        }
        
        int mid = getMid(ss,se);
        
        return max(getMaxUtil(ss,mid,qs,qe,2*si+1),getMaxUtil(mid+1,se,qs,qe,2*si+2));
    }
    
    
    int getMax(int n,int qs,int qe){
        
        if(qs > qe || qs < 0 || qe > n-1){
            return -1;
        }
        
        return getMaxUtil(0,n-1,qs,qe,0);
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());//for testcase
		String []temp = br.readLine().split(" ");//taking array as string
		int []arr = new int[t];
		for(int i=0;i<t;i++) //to convert array of string to array of integers
		{
		    arr[i] = Integer.parseInt(temp[i]); 
		}
		Segment tree = new Segment(arr,arr.length);
		//tree.print();
		int q = Integer.parseInt(br.readLine()); // no of queries
		while (q--!=0)
		{
		    String []temp1 = br.readLine().split(" ");
		    int s = Integer.parseInt(temp1[0]); //q1
		    int e = Integer.parseInt(temp1[1]); //q2
		 
		    System.out.println(tree.getMax(arr.length,s-1,e-1));   // maximum in range [q1,q2]
		    //System.out.println(getMax(arr,n,s,e));
		}
	}
}