LeetCode Solutions Blog

Range Sum Query - Mutable

Number: 307

Difficulty: Medium

Paid? No

Problem Description

Design a data structure that supports updating an element in an array and finding the sum of elements within a given range of indices. The operations should both be efficient, as there could be up to 3 * 10⁴ operations.

Key Insights

To efficiently support both point updates and range sum queries, a specialized data structure like a Binary Indexed Tree (Fenwick Tree) or a Segment Tree is ideal.
Both data structures provide update and sum query operations in O(log n) time.
The challenge is to maintain a mutable array while enabling fast sum computation over any specified range.

Space and Time Complexity

Time Complexity: O(log n) for both update and sumRange operations
Space Complexity: O(n) to store the additional tree structure

Solution

We can use a Binary Indexed Tree (Fenwick Tree) to solve this problem. The Fenwick Tree allows for efficient prefix sum calculations and point updates, both in O(log n) time. The approach involves:

Building the Fenwick Tree using the initial array.
On an update, computing the difference between the new value and the current value, then propagating the change appropriately in the tree.
For the sum range query, computing the prefix sum up to right and subtracting the prefix sum up to left-1.

Code Solutions

# Python implementation using a Binary Indexed Tree (Fenwick Tree)
class NumArray:
    def __init__(self, nums):
        # Store the original array
        self.nums = nums[:]  
        self.n = len(nums)
        # Initialize the BIT with 0s, size is (n+1) because BIT is 1-indexed
        self.tree = [0] * (self.n + 1)
        # Build the BIT: update tree for each value in the nums array
        for i, num in enumerate(nums):
            self._update_tree(i, num)

    def _update_tree(self, index, delta):
        # Update the BIT for index with delta change 
        i = index + 1  # Convert to 1-indexed for BIT operations
        while i <= self.n:
            self.tree[i] += delta  # Add delta to current tree node
            i += i & -i  # Move to the next responsible node

    def update(self, index, val):
        # Calculate the difference between new value and current value
        delta = val - self.nums[index]
        self.nums[index] = val  # Update the original array
        self._update_tree(index, delta)  # Update the BIT to reflect this change

    def _prefix_sum(self, index):
        # Compute the prefix sum from start up to and including index
        result = 0
        i = index + 1  # Convert to 1-indexed
        while i:
            result += self.tree[i]
            i -= i & -i  # Move to parent node
        return result

    def sumRange(self, left, right):
        # Return the sum of the range [left, right]
        return self._prefix_sum(right) - self._prefix_sum(left - 1) if left > 0 else self._prefix_sum(right)

# Example usage:
# numArray = NumArray([1, 3, 5])
# print(numArray.sumRange(0, 2))
# numArray.update(1, 2)
# print(numArray.sumRange(0, 2))