Discussion on: Algorithms: Range Sum Query

[Theofanis Despoudis]

For me, I would make it a little bit different. Notice that you don't need to use the cache as an array but just as a map. You just store the aggregated sum over all indices and when we ask for the sumRange we subtract the end from the first-1:

const NumArray = function(nums){
  this.cache = new Map();
  for (let i = 0; i < nums.length; i++){
      if (i === 0) { // First element
          this.cache.set(i,nums[i])
      } else {
          this.cache.set(i, this.cache.get(i-1) + nums[i]) // Every other element
      }
  }
}

NumArray.prototype.sumRange = function(i,j){
  return this.cache.get(j)-this.cache.get(i-1); // Just subtract the j index from the i-1 which is the sum of all array elements up to i.
}

new NumArray([1,2,3,4,5]).sumRange(2,4)

sumRange(2,4) -> cache(4) - cache(1) -> 15-3 = 12