Domain 2MediumCORE

Range Sum Query - Mutable

We are given an integer array nums and need to support two operations: updating a value at a specific index (update) and calculating the sum of elements within a specified range [left, right] (sumRange).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Binary Indexed Tree#Segment Tree

307. Range Sum Query - Mutable

Model: qwen3.5:9b
Topics: Binary Indexed Tree,Segment Tree
FAANG asked: 1
Acceptance rate: 36.9%


Problem Breakdown

We are given an integer array nums and need to support two operations: updating a value at a specific index (update) and calculating the sum of elements within a specified range [left, right] (sumRange).

Key Constraints & Implications:

  • Frequency: We can have up to 3×1043 \times 10^4 calls for both update and sumRange.
  • Naive Complexity: A simple array scan takes O(N)O(N) per query. With N=30,000N=30,000, a single update/query is fine (≈3⋅107\approx 3 \cdot 10^7 ops), but doing this repeatedly across many queries risks hitting Time Limits if the test cases are heavy on updates and ranges.
  • Data Types: Values can be negative (-100 to 100). Standard integer arithmetic handles negatives naturally, so no special handling is needed there. Overflow isn’t a concern in Python (arbitrary precision integers), but we should assume standard int behavior for logic design.

Intuition

To solve this efficiently, I need a data structure that supports both point updates and range sum queries faster than O(N)O(N).

  1. Naive Approach: Store the array directly. update is O(1)O(1) (direct assignment), but sumRange requires iterating from left to right, taking O(N)O(N). If we have many updates followed by sums, this degrades performance significantly over time.
  2. Prefix Sum Array: We can precompute prefix sums where prefix[i] = sum(nums[0...i]).
    • Query becomes O(1)O(1): sumRange(left, right) = prefix[right] - (left > 0 ? prefix[left-1] : 0).
    • Update breaks this structure. Changing one element invalidates all subsequent prefix sums in the array (O(N)O(N)).
  3. Optimal Structure: We need a dynamic structure that maintains these properties. A Segment Tree or a Binary Indexed Tree (Fenwick Tree) are standard candidates for range sum queries with updates.
    • Both offer O(log⁡N)O(\log N) complexity for both operations.
    • The Fenwick Tree is generally preferred here because it requires less code, has lower constant overhead, and is specifically optimized for prefix sums/updates compared to a generic Segment Tree implementation in Python.

Approach

I will implement the Binary Indexed Tree (Fenwick Tree).

Why BIT? It’s concise (O(N)O(N) space) and handles point updates efficiently by adding the difference between old and new values rather than overwriting nodes directly. The range sum is derived from prefix sums: sum(0..right) - sum(0..left-1).

Implementation Details:

  1. Initialization: We need a tree array of size N+1N+1 (BITs are typically 1-indexed to simplify the logic for powers of two and boundary conditions). I’ll map input index i to BIT index i + 1.
  2. Building: Instead of calling update NN times (O(Nlog⁡N)O(N \log N)), we can build in linear time, but given constraints, standard updates are acceptable. For clarity, I will use the loop-based construction which is robust and easy to follow.
  3. Update Logic: When update(index, val) is called:
    • Calculate delta = val - current_value[index].
    • Update internal state with new value.
    • Call BIT update function adding the delta at that index (and its ancestors).
  4. Query Logic:
    • Implement a helper _query(i) which returns sum from start to i in O(log⁡N)O(\log N).
    • Range sum is _query(right + 1) - _query(left).

Complexity Analysis

  • Time Complexity:
    • Initialization: O(Nlog⁡N)O(N \log N) (or O(N)O(N) with optimized build). Given constraints, this fits well.
    • update: O(log⁡N)O(\log N). We traverse up the tree structure adding deltas.
    • sumRange: $O(\log N)`. Two prefix queries and a subtraction.
  • Space Complexity: O(N)O(N) to store the BIT array and an auxiliary list for current values (to track changes).

Solution

class NumArray:
    
    def __init__(self, nums):
        self.nums = [0] * len(nums)  # Track current actual values
        n = len(nums)
        if n == 0: return
        
        # BIT array is 1-indexed for easier logic (index i covers range ending at i-1 in 0-based terms usually, 
        # but standard implementation uses index + 1). Size N+1.
        self.tree = [0] * (n + 1) 
        
        # Build the tree by adding each element's value to its position and ancestors
        for i, val in enumerate(nums):
            self._update(i, val)

    def _update(self, index: int, delta: int):
        """Adds delta to nums[index]"""
        idx = index + 1 # Convert to 1-based indexing
        
        while idx < len(self.tree):
            self.tree[idx] += delta
            idx += idx & (-idx)

    def _query(self, i: int) -> int:
        """Returns sum from nums[0...i-1] (inclusive in logic terms for BIT 1-based mapping)"""
        # In standard BIT query(i), we get prefix sum up to index i. 
        # Since our internal tree is size n+1 and maps input k to k+1:
        # We want sum(nums[0...i]). That corresponds to querying the bit at position (i + 1).
        
        idx = i + 1
        total = 0
        
        while idx > 0:
            total += self.tree[idx]
            idx -= idx & (-idx)
            
        return total

    def update(self, index: int, val: int):
        """Updates nums[index] to be val"""
        delta = val - self.nums[index]
        self._update(index, delta)
        self.nums[index] = val # Update our tracker
        
    def sumRange(self, left: int, right: int) -> int:
        """Returns sum of subarray nums[left...right]"""
        return self._query(right + 1) - self._query(left)

Edge Cases Handled

  • Negative Values: The logic relies on addition/subtraction. Since Python handles negative integers natively, sums involving negatives work correctly without modification.
  • Single Element Range (left == right): _query(right + 1) includes the element at right. _query(left) excludes it (since left is exclusive in prefix sum logic). The subtraction yields exactly that single value.
    • Example: Sum [2, 2]. Query(3) - Query(2). Correctly isolates index 2.
  • Index Bounds: Constraints ensure 0 <= index < nums.length and valid ranges for sums. BIT logic handles the internal mapping safely within these bounds.
  • Empty Array: While constraints say length >= 1, if it were empty, initialization checks would prevent errors (though not strictly required by problem statement).