Range Sum Query - Mutable

January 27, 2024

Problem Statement #

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 9 (sum of the first three elements)
   • numArray.update(1, 2); // update the second element to 2
   • numArray.sumRange(0, 2); // return 8 (sum of the first three elements)

Solution Approach #

The solution uses a Fenwick Tree (Binary Indexed Tree) for efficient updates and range sum queries.

Algorithm Steps #

1. Construct a Fenwick Tree with the given nums.
2. For update, adjust the Fenwick Tree with the difference between the new value and the current value at the index.
3. For sumRange, calculate the prefix sum up to right and left-1 using the Fenwick Tree, and return their difference.

Code (Python) #

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.nums = nums
        self.BIT = [0] * (self.n + 1)
        for i, num in enumerate(nums):
            self.init(i, num)
    
    def init(self, i, val):
        i += 1
        while i <= self.n:
            self.BIT[i] += val
            i += i & -i

    def update(self, index, val):
        diff = val - self.nums[index]
        self.nums[index] = val
        self.init(index, diff)

    def sum(self, i):
        res = 0
        i += 1
        while i:
            res += self.BIT[i]
            i -= i & -i
        return res

    def sumRange(self, left, right):
        return self.sum(right) - self.sum(left - 1)

# Test the class
numArray = NumArray([1, 3, 5])
print(numArray.sumRange(0, 2))  # Output: 9
numArray.update(1, 2)
print(numArray.sumRange(0, 2))  # Output: 8

Time Complexity #

• update: O(log n)
• sumRange: O(log n)

Space Complexity #

O(n), for the Fenwick Tree.