Interval Sum

Interval Sum

24%

Accepted

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.

Have you met this question in a real interview? 

Yes

Example

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

Note

We suggest you finish problem Segment Tree Build, Segment Tree Queryand Segment Tree Modify first.

Challenge

O(logN) time for each query

/**

 * 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) {

        // write your code here

         // write your code here

        long[] preSum = new long[A.length];

        long sum = 0;

        for(int i = 0; i < A.length; i++){

            sum += A[i];

            preSum[i] = sum;

        }

        ArrayList<Long> res = new ArrayList<Long>();

        for(int i = 0; i < queries.size(); i++){

            res.add(preSum[queries.get(i).end] - preSum[queries.get(i).start] + A[queries.get(i).start]);

        }

        return res;

    }

}