# Interval Sum

## Problem

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

Notice: We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

## Example

For array [1,2,7,8,5], and queries [(0,4),(1,2),(2,4)], return [23,9,20]

## Code - Java

/**
* Definition of Interval:
* public classs Interval {
*   int start, end;
*   Interval(int start, int end) {
*     this.start = start;
*     this.end = end;
*   }
* }
*/
public class Solution {
/**
* @param A, queries: Given an integer array and an query list
* @return: The result list
*/
public ArrayList<Long> intervalSum(int[] A,
ArrayList<Interval> queries) {
Node root = buildTree(A, 0, A.length - 1);
ArrayList<Long> result = new ArrayList<>();
for (Interval q : queries) {
}
return result;
}

private long query(Node root, Interval query) {
if (root == null) return 0;

if (root.start >= query.start && root.end <= query.end) {
return root.sum;
}
long left = query(root.left, query);
long right = query(root.right, query);
return left + right;
}

private Node buildTree(int[] A, int start, int end) {
if (start > end) return null;
if (start == end) return new Node(start, end, A[start]);
int mid = (start + end) / 2;
Node left = buildTree(A, start, mid);
Node right = buildTree(A, mid + 1, end);
Node root = new Node(start, end, left.sum + right.sum);
root.left = left;
root.right = right;
return root;
}

class Node {
int start, end;
long sum;
Node left, right;

public Node(int start, int end, long sum) {
this.start = start;
this.end = end;
this.sum = sum;
}
}
}