1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
    private int[] prefixArray;

    public NumArray(int[] nums) {
        int sum = 0;
        prefixArray = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            prefixArray[i] = sum;
        }
    }

    public int sumRange(int left, int right) {
        return left == 0 ? prefixArray[right] : prefixArray[right] - prefixArray[left - 1];
    }
}

Prefix sum.