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 calls for both
updateandsumRange. - Naive Complexity: A simple array scan takes per query. With , a single update/query is fine ( 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 .
- Naive Approach: Store the array directly.
updateis (direct assignment), butsumRangerequires iterating fromlefttoright, taking . If we have many updates followed by sums, this degrades performance significantly over time. - Prefix Sum Array: We can precompute prefix sums where
prefix[i] = sum(nums[0...i]).- Query becomes :
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 ().
- Query becomes :
- 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 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 ( 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:
- Initialization: We need a tree array of size (BITs are typically 1-indexed to simplify the logic for powers of two and boundary conditions). I’ll map input index
ito BIT indexi + 1. - Building: Instead of calling update times (), 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.
- 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).
- Calculate delta =
- Query Logic:
- Implement a helper
_query(i)which returns sum from start toiin . - Range sum is
_query(right + 1) - _query(left).
- Implement a helper
Complexity Analysis
- Time Complexity:
- Initialization: (or with optimized build). Given constraints, this fits well.
update: . We traverse up the tree structure adding deltas.sumRange: $O(\log N)`. Two prefix queries and a subtraction.
- Space Complexity: 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 atright._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.
- Example: Sum
- Index Bounds: Constraints ensure
0 <= index < nums.lengthand 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).