Sum Between Range

You are given an integer array nums that does not change, and you will be asked multiple queries of the form (left, right), where each query asks for the sum of nums[left..right] (inclusive on both ends).

Design a solution that answers each query in O(1) time after an initial O(n) preprocessing step. A naive solution that re-sums the subarray on every query is too slow when there are many queries against a large array.

Implement a class RangeSumQuery with:

• __init__(self, nums: List[int]) — preprocesses the array.
• sum_range(self, left: int, right: int) -> int — returns the sum of nums[left..right] inclusive, where 0 <= left <= right < len(nums).

Example 1

nums = [-2, 0, 3, -5, 2, -1]
rsq = RangeSumQuery(nums)
rsq.sum_range(0, 2)   # -2 + 0 + 3 = 1
rsq.sum_range(2, 5)   # 3 + -5 + 2 + -1 = -1
rsq.sum_range(0, 5)   # sum of entire array = -3

Example 2

nums = [4, 4, 4, 4]
rsq = RangeSumQuery(nums)
rsq.sum_range(1, 3)   # 4 + 4 + 4 = 12

Constraints

• 1 <= len(nums) <= 10^5
• -10^5 <= nums[i] <= 10^5
• 0 <= left <= right < len(nums)
• sum_range may be called up to 10^4 times.