303. Range Sum Query - Immutable

Problem Overview

Prefix sums let any range sum query run in O(1) after O(n) preprocessing.

Intuition

Prefix sums let any range sum query run in O(1) after O(n) preprocessing. prefix[i] stores sum of nums[0..i-1], so sum(l,r) = prefix[r+1] - prefix[l]. The array never changes after construction.

Algorithm

1Build prefix array of length n+1 with prefix[0]=0.
2For i from 1 to n: prefix[i] = prefix[i-1] + nums[i-1].
3SumRange(l,r): return prefix[r+1] - prefix[l].

Example Walkthrough

Input: nums = [-2,0,3,-5,2,-1], l=0, r=2

1.prefix = [0,-2,-2,1,-4,-2,-3].
2.SumRange(0,2) = prefix[3]-prefix[0] = 1-0 = 1.

Output: 1

Common Pitfalls

•prefix has length n+1; prefix[0]=0 sentinel simplifies range formula.
•Use long if values can overflow int in prefix.
•Immutable — no updates to nums after build.

303.cs

// Approach: Prefix sum array for O(1) range queries after O(n) preprocessing.
// preSum[i] stores the sum of nums[0..i-1], with preSum[0] = 0 as a sentinel.
// Range sum query [left, right] = preSum[right + 1] - preSum[left].
// The sentinel avoids a boundary check for left == 0.
// This pattern extends to 2D (304), trees (307 Fenwick tree), and strings.
// Time: O(n) preprocessing, O(1) per query. Space: O(n) for the prefix array.

public class NumArray
{

    int[] preSum;
    public NumArray(int[] nums)
    {
        int m = nums.Length;
        preSum = new int[m + 1];
        int sum = 0;
        for (int i = 0; i < m; i++)
        {
            sum += nums[i];
            preSum[i + 1] = sum;
        }
    }

    public int SumRange(int left, int right)
    {
        return preSum[right + 1] - preSum[left];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.SumRange(left,right);
 */

Was this solution helpful?