Skip to content

307. Range Sum Query - Mutable

Difficulty Topics

Description

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

  1. Update the value of an element in nums.
  2. 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.
  • void update(int index, int val) Updates the value of nums[index] to be val.
  • 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", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • At most 3 * 104 calls will be made to update and sumRange.

Solution

range-sum-query-mutable.py
class BinaryIndexedTree:
    def __init__(self, size):
        self._size = size + 1
        self._data = [0] * self._size

    @staticmethod
    def from_list(nums):
        tree = BinaryIndexedTree(len(nums))
        for index, num in enumerate(nums):
            tree.update(index, num)
        return tree

    def update(self, index, value):
        index += 1
        while index < self._size:
            self._data[index] += value
            index += index & -index

    def query(self, index):
        index += 1
        result = 0
        while index > 0:
            result += self._data[index]
            index -= index & -index
        return result

    def range_sum(self, left, right):
        return self.query(right) - self.query(left - 1)

class NumArray:
    def __init__(self, nums: List[int]):
        self._tree = BinaryIndexedTree.from_list(nums)
        self._nums = nums

    def update(self, index: int, val: int) -> None:
        self._tree.update(index, val - self._nums[index])
        self._nums[index] = val

    def sumRange(self, left: int, right: int) -> int:
        return self._tree.range_sum(left, right)