NUHMAN.com

Introduction

LeetCode 307: Range Sum Query - Mutable is a dynamic range sum problem that involves both updates and range sum queries on an array. The key challenge is to efficiently calculate the sum of elements in a range, while also allowing updates to individual elements of the array. A brute-force solution would require recalculating the sum for every query, which is inefficient for large arrays and many queries. Instead, we use a Fenwick Tree (also known as Binary Indexed Tree, BIT) to perform both operations in logarithmic time.

Problem Statement

Given an integer array nums, perform the following operations:

• update(index, val): Update the element at index index to be val.
• sumRange(left, right): Return the sum of the elements in the array between indices left and right (inclusive).

The operations need to be performed efficiently, and the updates should be mutable (i.e., modifying the array).

Example

python

# 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); // returns 9 = sum([1,3,5])
    numArray.update(1, 2);   // nums = [1,2,5]
    numArray.sumRange(0, 2); // returns 8 = sum([1,2,5])

✅ Step-by-Step Solution

🧠 Intuition

This problem involves two main operations:

1. Range Sum Queries: Efficiently calculate the sum of elements between indices left and right.
2. Updates: Modify the value at a specific index and adjust the data structure to reflect this change.

The brute force approach would involve recalculating the sum for each query, which would take O(n) time for each query, making it inefficient for large arrays and many queries. Instead, we can use a Fenwick Tree (Binary Indexed Tree), which allows:

• Point updates (modifying the value of an element) in O(log n) time.
• Range sum queries in O(log n) time.

This ensures both operations are efficient, and the solution scales well.

✅ Approach

1. Fenwick Tree (Binary Indexed Tree):

• A Fenwick Tree supports both point updates and prefix sum queries in O(log n) time.
• The tree allows us to efficiently update an element and recalculate the prefix sum to support range queries.

1. Operations:

• update(index, val): Update the element at the specified index to val. We compute the difference between the new value and the current value, and then propagate this difference through the Fenwick Tree.
• sumRange(left, right): To get the sum of the range from index left to index right, we compute the prefix sum up to right and subtract the prefix sum up to left-1 (using the Fenwick Tree).

1. Fenwick Tree Structure:

• The Fenwick Tree is represented as an array where each element contains the sum of certain elements from the original array.
• update(idx, val): Add val to the Fenwick Tree at the given index and propagate the update.
• query(idx): Get the sum of elements from the beginning of the array to index idx.

1. Space Complexity:

• The space complexity of the solution is O(n) to store the Fenwick Tree.

✅ Python Code

python

class NumArray:

    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.nums = nums
        self.bit = [0] * (self.n + 1)  # Fenwick Tree (1-based index)
        
        # Initialize Fenwick Tree with initial values
        for i in range(self.n):
            self.update(i, nums[i])

    def update(self, i: int, val: int) -> None:
        # Convert index to 1-based
        i += 1
        diff = val - self.nums[i - 1]
        self.nums[i - 1] = val
        
        # Update Fenwick Tree with the difference
        while i <= self.n:
            self.bit[i] += diff
            i += i & -i  # Move to the next index in Fenwick Tree
    
    def sumRange(self, left: int, right: int) -> int:
        # Convert indices to 1-based
        left += 1
        right += 1
        
        # Query for the sum up to index `right`
        def query(idx: int) -> int:
            total = 0
            while idx > 0:
                total += self.bit[idx]
                idx -= idx & -idx  # Move to the parent in Fenwick Tree
            return total
        
        return query(right) - query(left - 1)

🧪 How It Works

1. Constructor (__init__):

• The constructor initializes the nums array and creates an auxiliary Fenwick Tree (bit) to manage the sums.
• It iterates over the nums array and populates the Fenwick Tree by calling the update() method.

1. update(i, val):

• To update the value at index i, we calculate the difference between the new value (val) and the old value (self.nums[i]).
• This difference is propagated to the Fenwick Tree, updating all relevant nodes.

1. sumRange(left, right):

• The sumRange function calculates the sum of elements between indices left and right.
• It uses the query method to get the prefix sum up to right and left-1, and then returns the difference to get the range sum.

1. query(idx):

• The query method computes the prefix sum from the beginning of the array to the specified index idx.
• It traverses the Fenwick Tree to sum up the relevant values.

⏱️ Time and Space Complexity

MetricValueTime Complexity (update)O(log n)Time Complexity (sumRange)O(log n)Space ComplexityO(n)

• Time Complexity (update): Each update operation modifies the Fenwick Tree in O(log n) time, where n is the length of the array.
• Time Complexity (sumRange): Each range sum query is answered in O(log n) time by querying the Fenwick Tree.
• Space Complexity: The space complexity is O(n), where n is the number of elements in the array, as we store the Fenwick Tree.

🔍 Edge Cases

1. Empty Array:

• If the array is empty, handle the initialization and operations gracefully (e.g., prevent updates and sum queries).

1. Multiple Updates to Same Index:

• If the same index is updated multiple times, the update method will correctly compute the new value by considering the difference from the previous value.

1. Range Queries on Small Arrays:

• Ensure that sum queries on small arrays (e.g., size 1 or 2) work correctly without any off-by-one errors.

✅ Conclusion

LeetCode 307: Range Sum Query - Mutable is an excellent problem that involves efficiently handling both updates and range sum queries on an array. Using a Fenwick Tree (Binary Indexed Tree) allows us to perform both operations in O(log n) time, making the solution scalable for large inputs. The solution uses an elegant combination of update propagation and prefix sum queries to maintain efficient time complexity.