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) {
            result.add(query(root, q));
        }
        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;
        }
    }
}