Range Sum Query - Immutable

Description

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

 

Constraints:

• You may assume that the array does not change.
• There are many calls to sumRange function.
• 0 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5
• 0 <= i <= j < nums.length

Solution(javascript)

/** Prefix Sum
 * @param {number[]} nums
 */
const NumArray = function (nums) {
  nums.forEach((num, index) => {
    nums[index] = (nums[index - 1] || 0) + num
  })
  this.nums = nums
}

/**
 * @param {number} i
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function (i, j) {
  return this.nums[j] - (this.nums[i - 1] || 0)
}