Code Logo

Range Sum Query - Immutable

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an integer array nums, implement a class that supports queries: sumRange(left, right) which returns the sum of elements from index left to right inclusive. The array does not change between queries (immutable). The naive approach recomputes the sum each query in O(n), but prefix sums enable O(1) per query with O(n) preprocessing.

The prefix sum array is a classic DP pattern: pre[i] stores the sum of nums[0] through nums[i-1]. The sum of range [left, right] is then pre[right + 1] - pre[left]. This uses the difference of two prefix sums to isolate the subarray sum.

The construction of the prefix array takes O(n) time and O(n) space. Each query runs in O(1) time by simple subtraction. This is the foundation of more complex DP problems like 2D range sum queries.

Edge cases include left = right (sum of a single element), left = 0 (prefix sum up to right), and an empty array (return 0 for any query).

Prefix sums are the simplest form of 1D DP: each prefix sum builds on the previous one. This technique extends to 2D for matrix range sums, where O(mn) preprocessing enables O(1) queries for any rectangular submatrix.

This fundamental technique appears in many more complex DP problems like 2D range sum.

Example Input & Output

Example 1
Input
NumArray([1]), sumRange(0,0)
Output
1
Explanation

Single element.

Example 2
Input
NumArray([1,2,3]), sumRange(1,2)
Output
5
Explanation

2+3=5.

Example 3
Input
NumArray([5]), sumRange(0,0)
Output
5
Explanation

Single query.

Example 4
Input
NumArray([1,1,1,1]), sumRange(0,3)
Output
4
Explanation

Sum of all four 1s.

Example 5
Input
NumArray([-2,0,3,-5,2,-1]), sumRange(0,2), sumRange(2,5), sumRange(0,5)
Output
1,-1,-3
Explanation

Prefix sums enable O(1) queries.

Algorithm Flow

Recommendation Algorithm Flow for Range Sum Query - Immutable
Recommendation Algorithm Flow for Range Sum Query - Immutable

Solution Approach

Build prefix sum array of length n+1 with pre[0]=0. For each i, pre[i+1] = pre[i] + nums[i]. SumRange returns pre[right+1] - pre[left].

function solution(nums) {
  var pref = [0];
  for (var i = 0; i < nums.length; i++) {
    pref.push(pref[i] + nums[i]);
  }
  return {
    sumRange: function(left, right) {
      return pref[right + 1] - pref[left];
    }
  };
}

Build O(n), Query O(1), Space O(n).

Best Answers

java
class NumArray {
    private int[] pref;
    public NumArray(int[] nums) {
        pref = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            pref[i + 1] = pref[i] + nums[i];
        }
    }
    public int sumRange(int left, int right) {
        return pref[right + 1] - pref[left];
    }
}