public ArrayList<Long> intervalSum(int[] A, 
                                       ArrayList<Interval> queries) {
        // write your code here
        long[] prefixSum = new long[A.length+1];
        for (int i=0; i<A.length; i++) {
            prefixSum[i+1] = prefixSum[i] + A[i];
        }
        ArrayList<Long> res = new ArrayList<Long>();
        for (Interval interval : queries) {
            int start = interval.start;
            int end = interval.end;
            long result = prefixSum[end+1] - prefixSum[start];
            res.add(result);
        }
        return res;
    }