Given an integer array A[n], there are repeated queries asking for the sum between A[i] and A[j]. what should we do to speed up the query.

Assumption: the array is not null.

Approach: preprocess. get the sum of each element from 0 th element to i_th element, including _i_th element.

sum(i-j) = m[j] - m[i] + array[i].

Code:

public class Solution{
    public int query(int[] array, int start, int end) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int[] preSum = new int[array.length];
        preSum[0] = array[0];

        for (int i = 1; i < array.length; i++) {
            preSum[i] = preSum[i - 1] + array[i];
        }
        int result = 0;   
        result = preSum[end] - preSum[start] + array[start];
        return result;
    }
}

Time: O(n).