Range Sum Query - Immutable

Problem

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

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]).

Constraints

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105
• 0 <= left <= right < nums.length
• At most 104 calls will be made to sumRange.

Solution

The problem Range Sum Query - Immutable can be solved by creating an array of prefix sums. Let prefix sum Sn = a1 + a2 + ... + an. Then, sum of elements between indices left and right inclusive is equal to Sright - Sleft-1 as Sright - Sleft-1 = (a1 + a2 + ... + aright) - (a1 + a2 + ... + aleft-1) = aleft + aleft+1 + ... + aright.

Implementation

class NumArray
{
  private:
    int _nums[10001];

  public:
    NumArray(vector<int> &nums)
    {
        for (int i = 0; i < nums.size(); i++)
            _nums[i + 1] = nums[i] + _nums[i];
    }

    int sumRange(int left, int right) { return _nums[right + 1] - _nums[left]; }
};

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