Continuing the discussion from Discussion About MAXIMUM SUM QUERY:
package competitive;
import java.util.*;
public class MaxsuminGivenrange {
private class Node {
int data;
int startInterval;
int endInterval;
Node left;
Node rigth;
}
private Node root;
public MaxsuminGivenrange(int arr[]) {
// TODO Auto-generated constructor stub
this.root = ConstructTree(arr, 0, arr.length - 1);
}
private Node ConstructTree(int[] arr, int si, int ei) {
// TODO Auto-generated method stub
Node node = new Node();
node.startInterval = si;
node.endInterval = ei;
if (si == ei) {
Node nn = new Node();
nn.data = arr[si];
nn.startInterval = si;
nn.endInterval = ei;
return nn;
}
int mid = (si + ei) / 2;
node.left = ConstructTree(arr, si, mid);
node.rigth = ConstructTree(arr, mid + 1, ei);
node.data =Math.max(node.rigth.data,Math.max(node.left.data,(node.left.data + node.rigth.data)));
return node;
}
public int sumofinterval(int s, int e) {
return sumofinterval(this.root, s, e);
}
private int sumofinterval(Node node, int s, int e) {
// TODO Auto-generated method stub
if (node.startInterval > e) {
return 0;
}
// node completely lying;
if (node.startInterval >= s && node.endInterval <= e) {
return node.data;
} else if (node.startInterval > e || node.endInterval < s) {
return 0;
} else {
int leftans = sumofinterval(node.left, s, e);
int rightans = sumofinterval(node.rigth, s, e);
return leftans + rightans;
}
// return 0;
}
public static void main(String args[]) {
// Your Code Here
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int [n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
MaxsuminGivenrange t = new MaxsuminGivenrange(arr);
// t.display();
int Q = sc.nextInt();
while(Q-- >0){
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(t.sumofinterval(a-1,b-1));
}
}
}