Solution
Approach #1 (Brute Force) [Time Limit Exceeded]
Each time sumRange is called, we use a for loop to sum each individual element from index to .
private int[] data; public NumArray(int[] nums) { data = nums; } public int sumRange(int i, int j) { int sum = 0; for (int k = i; k <= j; k++) { sum += data[k]; } return sum; }
Complexity analysis:

Time complexity : time per query. Each sumRange query takes time.

Space complexity : . Note that
data
is a reference tonums
and is not a copy of it.
Approach #2 (Caching) [Accepted]
Imagine that sumRange is called one thousand times with the exact same arguments. How could we speed that up?
We could trade in extra space for speed. By precomputing all range sum possibilities and store its results in a hash table, we can speed up the query to constant time.
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>(); public NumArray(int[] nums) { for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; map.put(Pair.create(i, j), sum); } } } public int sumRange(int i, int j) { return map.get(Pair.create(i, j)); }
Complexity analysis

Time complexity : time per query, time precomputation. The precomputation done in the constructor takes time. Each sumRange query's time complexity is as the hash table's look up operation is constant time.

Space complexity : . The extra space required is as there are candidates for both and .
Approach #3 (Caching) [Accepted]
The above approach takes a lot of space, could we optimize it?
Imagine that we precompute the cummulative sum from index to . Could we use this information to derive ?
Let us define as the cumulative sum for (inclusive):
Now, we can calculate sumRange as following:
private int[] sum; public NumArray(int[] nums) { sum = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { sum[i + 1] = sum[i] + nums[i]; } } public int sumRange(int i, int j) { return sum[j + 1]  sum[i]; }
Notice in the code above we inserted a dummy 0 as the first element in the sum array. This trick saves us from an extra conditional check in sumRange function.
Complexity analysis

Time complexity : time per query, time precomputation. Since the cumulative sum is cached, each sumRange query can be calculated in time.

Space complexity : .