Range Sum Query – Immutable

Design a class NumArray:

• NumArray(nums) stores the integer array nums.
• sum_range(left, right) returns the sum of nums[left..right], both ends included.

The array never changes, but sum_range may be called many times, so make each call fast.

Example 1

Input:
["NumArray", "sum_range", "sum_range", "sum_range"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output: [None, 1, -1, -3]

-2 + 0 + 3 = 1; 3 - 5 + 2 - 1 = -1; the whole array sums to -3.

Example 2

Input:
["NumArray", "sum_range"]
[[[5]], [0, 0]]
Output: [None, 5]

Example 3

Input:
["NumArray", "sum_range", "sum_range", "sum_range"]
[[[1, 2, 3, 4]], [1, 2], [0, 3], [3, 3]]
Output: [None, 5, 10, 4]

Constraints

• 1 ≤ len(nums) ≤ 2 · 10⁴
• -10⁵ ≤ nums[i] ≤ 10⁵
• 0 ≤ left ≤ right < len(nums)
• up to 2 · 10⁴ calls to sum_range