## 303. Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (ij), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3


Note:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Brute Force) [Time Limit Exceeded]

\n

Each time sumRange is called, we use a for loop to sum each individual element from index to .

\n
private int[] data;\n\npublic NumArray(int[] nums) {\n    data = nums;\n}\n\npublic int sumRange(int i, int j) {\n    int sum = 0;\n    for (int k = i; k <= j; k++) {\n        sum += data[k];\n    }\n    return sum;\n}\n
\n

Complexity analysis:

\n
\n
• \n

Time complexity : time per query.\nEach sumRange query takes time.

\n
• \n
• \n

Space complexity : . Note that data is a reference to nums and is not a copy of it.

\n
• \n
\n
\n

#### Approach #2 (Caching) [Accepted]

\n

Imagine that sumRange is called one thousand times with the exact same arguments. How could we speed that up?

\n

We could trade in extra space for speed. By pre-computing all range sum possibilities and store its results in a hash table, we can speed up the query to constant time.

\n
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();\n\npublic NumArray(int[] nums) {\n    for (int i = 0; i < nums.length; i++) {\n        int sum = 0;\n        for (int j = i; j < nums.length; j++) {\n            sum += nums[j];\n            map.put(Pair.create(i, j), sum);\n        }\n    }\n}\n\npublic int sumRange(int i, int j) {\n    return map.get(Pair.create(i, j));\n}\n
\n

Complexity analysis

\n
\n
• \n

Time complexity : time per query, time pre-computation.\nThe pre-computation done in the constructor takes time. Each sumRange query\'s time complexity is as the hash table\'s look up operation is constant time.

\n
• \n
• \n

Space complexity : .\nThe extra space required is as there are candidates for both and .

\n
• \n
\n
\n

#### Approach #3 (Caching) [Accepted]

\n

The above approach takes a lot of space, could we optimize it?

\n

Imagine that we pre-compute the cummulative sum from index to . Could we use this information to derive ?

\n

Let us define as the cumulative sum for (inclusive):

\n

\n\n

\n

Now, we can calculate sumRange as following:

\n

\n\n

\n
private int[] sum;\n\npublic NumArray(int[] nums) {\n    sum = new int[nums.length + 1];\n    for (int i = 0; i < nums.length; i++) {\n        sum[i + 1] = sum[i] + nums[i];\n    }\n}\n\npublic int sumRange(int i, int j) {\n    return sum[j + 1] - sum[i];\n}\n
\n

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.

\n

Complexity analysis

\n
\n
• \n

Time complexity : time per query, time pre-computation.\nSince the cumulative sum is cached, each sumRange query can be calculated in time.

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
'