About
Life
Daily Notes

303. Range Sum Query - Immutable

3 min read

Date: 02-09-2025 Time: 09:19

Given an integer array nums, handle multiple queries of the following type:

  1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input

["NumArray", "sumRange", "sumRange", "sumRange"]
[[ [-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 (-2) + 0 + 3 = 1

numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1

numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

SOLUTION:

I coded up the most obvious solution i can think of - it is very simple

class NumArray {
public:
    vector<int> prefixSum;
    NumArray(vector<int>& nums) {
        int n = nums.size();
        prefixSum.resize(n); 
        prefixSum[0] = nums[0];
        for(int i=1;i<n;i++){
            prefixSum[i] = nums[i] + prefixSum[i-1];
        }
    }
    
    int sumRange(int left, int right) {
        if (left==0) return prefixSum[right];
        return prefixSum[right] - prefixSum[left-1];
    }
};
 
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

IMPORTANT

FINDING PREFIX SUM INPLACE:

vector<int> nums = {2, 4, 6, 8};
for (int i = 1; i < nums.size(); i++) {
    nums[i] += nums[i - 1];
}

OPTIMISED

class NumArray {
public:
    vector<int>& preSum; 
    
    NumArray(vector<int>& nums) : preSum(nums) {
        for (int i = 1; i < preSum.size(); ++i)
            preSum[i] += preSum[i-1]; 
    }
    
    int sumRange(int left, int right) {
        if (left == 0) return preSum[right];
        return preSum[right] - preSum[left-1];
    }
};

The line

NumArray(vector<int>& nums) : preSum(nums)

is a constructor with a member initializer list in C++.

1. What’s happening here?

  • NumArray(vector<int>& nums) is the constructor of the class NumArray.

  • The part after the colon : preSum(nums) is called a member initializer list.

  • It means: “Initialize the data member preSum with nums.”

2. Why do we need it?

Normally, in a constructor you might see:

NumArray(vector<int>& nums) { preSum = nums; }

But the problem is:

  • preSum is declared as a reference (vector<int>& preSum).

  • References in C++ must be initialized at the time of construction. You cannot assign to them later.

So the only way to bind preSum to nums is through the initializer list.

3. Step by step in your case

  • vector<int>& preSum; → a reference to a vector<int>.

  • In the constructor:

NumArray(vector<int>& nums) : preSum(nums)

  • This binds preSum to the same vector object nums refers to.

  • After this, preSum and nums both point to the same underlying vector. Any change in preSum will affect nums.

In short:
: preSum(nums) is telling the compiler:
“When constructing NumArray, bind the member reference preSum to the vector nums passed in.”

Graph View