Range Sum Query - Immutable

Prefix SumArray

15 min

Problem Statement

Given an integer array nums, handle multiple queries of calculating the sum of the elements between indices left and right inclusive.

Implement the NumArray class:

NumArray(int[] nums) Initializes the object.
int sumRange(int left, int right) Returns the sum of the subarray nums[left...right].

Example

Example 1:

operations: ["NumArray","sumRange","sumRange","sumRange"]

inputs: [[-2,0,3,-5,2,-1],[0,2],[2,5],[0,5]]

Output: [null,1,-1,-3]

Explanation:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

Solution

To handle many `sumRange` queries efficiently, we can pre-calculate a prefix sum array. The prefix sum at index `i` stores the sum of all elements from the start of the array up to index `i-1`.

With this `prefix` array, the sum of any range `[left, right]` can be found in O(1) time by calculating `prefix[right + 1] - prefix[left]`. This avoids re-calculating sums for each query.

Algorithm Steps

Create a `prefix_sum` array of size `n + 1`.
Iterate through the input `nums`, calculating the cumulative sum at each position and storing it in `prefix_sum`.
For `sumRange(left, right)`, return `prefix_sum[right + 1] - prefix_sum[left]`.

Range Sum Query

Interactive Prefix Sum

Original Array (nums)

-2

-5

-1

Prefix Sum Array

-2

-4

-2

-3

Left:

Right:

Range Sum Query - Immutable


class NumArray:
    def __init__(self, nums: list[int]):
        self.prefix_sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix_sum[i+1] = self.prefix_sum[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix_sum[right + 1] - self.prefix_sum[left]