Range Sum Query - Immutable

Problem

Design a class NumArray that is constructed from an integer array nums and then answers many queries of the form sumRange(left, right): the sum of the elements from index left through index right, inclusive. The array never changes after construction, and there may be far more queries than elements.

• The array is non-empty and has at most 50,000 elements.
• Elements are integers with magnitude at most 100,000.
• Every query satisfies 0 <= left <= right < len(nums).
• Expect tens of thousands of queries against one array.

Examples

• NumArray([4, -3, 8, 1, -6, 5]): sumRange(0, 2) → 9 (4 - 3 + 8), sumRange(1, 4) → 0, sumRange(0, 5) → 9.
• NumArray([-9]): sumRange(0, 0) → -9.
• NumArray([2, 2, 2, 2, 2]): sumRange(1, 3) → 6, sumRange(2, 2) → 2.

Hints

1. Summing the slice on every query is O(n) per call; with many queries that adds up. What can you precompute once?
2. If you knew the sum of every prefix, the sum of any range would be a subtraction.
3. Build prefix[i] = sum(nums[:i]) with prefix[0] = 0; then sumRange(l, r) = prefix[r + 1] - prefix[l].