algoadvance

The problem “Range Sum Query - Mutable” from LeetCode requires designing a data structure that supports both range sum queries and updates on an array.

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:

numArray = NumArray([1, 3, 5])
numArray.sumRange(0, 2)  # return 9
numArray.update(1, 2)    # nums = [1, 2, 5]
numArray.sumRange(0, 2)  # return 8

Clarifying Questions

1. What is the size range of the input array?
   • Typically, constraints say around 1 <= nums.length <= 3 * 10^4.
2. What are the value ranges for elements in the array?
   • Normally, values range around -10^5 <= nums[i] <= 10^5.
3. What kind of operations should be optimized, updates or queries, or both equally?
   • The structure should optimize both the update and the range sum queries.

Strategy

To efficiently manage both updates and range sum queries, we’ll employ a Segment Tree:

• Initialization: Build a segment tree from the input array nums.
• Update: Adjust the segment tree when an element of the input array is updated.
• Range Sum Query: Query the segment tree to get the sum of a range.

Code

Here is the implementation of the NumArray using a segment tree:

class NumArray:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        if self.n > 0:
            self.tree = [0] * (2 * self.n)
            self.buildTree(nums)
    
    def buildTree(self, nums: List[int]):
        # Insert leaf nodes in tree
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        # Build the tree by calculating parents
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]
    
    def update(self, index: int, val: int):
        # Set value at position p
        pos = index + self.n
        self.tree[pos] = val
        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[pos * 2] + self.tree[pos * 2 + 1]
    
    def sumRange(self, left: int, right: int) -> int:
        # Get sum of elements nums[left..right]
        l = left + self.n
        r = right + self.n
        sum = 0
        while l <= r:
            if l % 2 == 1:
                sum += self.tree[l]
                l += 1
            if r % 2 == 0:
                sum += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return sum

Time Complexity

• Initialization (__init__ and buildTree): O(n), where n is the length of the array, as building the segment tree requires processing each element once.
• Update (update): O(log n), as we need to propagate the update to the root in a balanced binary tree.
• Range Sum Query (sumRange): O(log n), as we typically traverse up to twice the height of the segment tree for the sum calculation.

This solution ensures efficient handling of both updates and range sum queries, suitable for large input sizes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?