Range Sum Query - Immutable

01 · Question

Given an integer array nums, handle multiple queries of the form sumRange(left, right) returning the sum of elements between left and right inclusive.

02 · Analysis

Store pref[i] as the sum of the first i values, with pref[0]=0. For inclusive [left,right], subtract pref[left] from pref[right+1]; the shared earlier prefix cancels. Construction costs O(n) time/space; each valid query costs O(1). Negative values and left=0 require no special branch. The input remains unchanged after construction.

03 · Solution

Reference solution

1class NumArray:
2    def __init__(self, nums: List[int]):
3        self.pref = [0]
4        for x in nums:
5            self.pref.append(self.pref[-1] + x)
6
7    def sumRange(self, left: int, right: int) -> int:
8        return self.pref[right + 1] - self.pref[left]

Subarray Sum Equals K