Range Sum Query - Mutable

Description

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

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

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

 

Constraints:

• The array is only modifiable by the update function.
• You may assume the number of calls to update and sumRange function is distributed evenly.
• 0 <= i <= j <= nums.length - 1

Solution(javascript)

/* eslint-disable no-bitwise */


/** Binary Indexed Tree https://www.youtube.com/watch?v=GURRzAKL1lY&feature=emb_logo
 * @param {number[]} nums
 */
const NumArray = function (nums) {
  const parent = i => i - (i & -i)
  const bitArr = [0]
  for (const num of nums) {
    bitArr.push(bitArr[bitArr.length - 1] + num)
  }
  for (let i = bitArr.length - 1; i > 0; i--) {
    const parentIndex = parent(i)
    if (parentIndex >= 0) {
      bitArr[i] -= bitArr[parentIndex]
    }
  }
  this.nums = nums
  this.bitArr = bitArr
  this.parent = parent
  this.next = i => i + (i & -i)
}

/**
 * @param {number} i
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function (i, val) {
  const diff = val - this.nums[i]
  let current = i + 1
  this.nums[i] = val
  while (current <= this.bitArr.length - 1) {
    this.bitArr[current] += diff
    current = this.next(current)
  }
}

/**
 * @param {number} i
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function (i, j) {
  let res = 0
  let currentEnd = j + 1
  let currentStart = i
  while (currentEnd > 0) {
    res += this.bitArr[currentEnd]
    currentEnd = this.parent(currentEnd)
  }
  while (currentStart > 0) {
    res -= this.bitArr[currentStart]
    currentStart = this.parent(currentStart)
  }
  return res
}