Range Sum Query - Immutable

easy LeetCode #303
array design prefix-sum

Description

Given an integer array nums, handle multiple queries of the following type: Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement a function that takes an array nums and a list of queries, where each query is [left, right], and returns a list of sums for each query.

Example 1:
Input: nums = [-2, 0, 3, -5, 2, -1], queries = [[0, 2], [2, 5], [0, 5]]
Output: [1, -1, -3]
Explanation:
- Query [0, 2]: nums[0] + nums[1] + nums[2] = -2 + 0 + 3 = 1
- Query [2, 5]: nums[2] + nums[3] + nums[4] + nums[5] = 3 + (-5) + 2 + (-1) = -1
- Query [0, 5]: nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5] = -2 + 0 + 3 + (-5) + 2 + (-1) = -3

Example 2:
Input: nums = [1, 2, 3, 4, 5], queries = [[0, 4], [1, 3], [2, 2]]
Output: [15, 9, 3]
Explanation:
- Query [0, 4]: 1 + 2 + 3 + 4 + 5 = 15
- Query [1, 3]: 2 + 3 + 4 = 9
- Query [2, 2]: 3 (single element)

Example 3:
Input: nums = [5], queries = [[0, 0]]
Output: [5]
Explanation: Single element array, query returns that element.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= left <= right < nums.length
  • At most 10^4 calls will be made to sumRange

Complexity

Show Complexity
  • Time: O(n) preprocessing, O(1) per query
  • Space: O(n)

Hints

Show Hints
Pattern
Prefix sum array
Approach
Create prefix[i] = sum of nums[0..i-1]. Then sumRange(l,r) = prefix[r+1] - prefix[l]
Complexity
Build prefix sum in O(n), answer each query in O(1)

Solutions

Show PY Solution 
def solution(nums, queries):
    sums = [0]
    for i in range(len(nums)):
        sums.append(nums[i] + sums[-1])

    # print(sums)
    results = []
    for l, r in queries:
        # print(l, r, sums[r], sums[l])
        results.append(sums[r + 1] - sums[l])

    return results