Skip to main content

307 - Range Sum Query - Mutable

Difficulty: Medium | Pattern: Segment Tree / Binary Indexed Tree | Company tags: Google, Amazon, Microsoft

Problem Statement​

Given an integer array nums, handle multiple queries of the following types:

  1. Update the value of an element in nums.
  2. Calculate the sum of the elements of nums between indices left and right (inclusive).

Implement the NumArray class with O(log n) time for both operations.

Example:

NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2) → 9
numArray.update(1, 2)   → nums becomes [1,2,5]
numArray.sumRange(0, 2) → 8

Approach: Binary Indexed Tree (Fenwick Tree) — O(log n) per operation​

Key insight: A Fenwick tree stores prefix sums and updates propagate through specific bit-based parent links in O(log n).

Algorithm Flow​

class NumArray:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.tree = [0] * (self.n + 1)
        self.nums = nums[:]
        for i, v in enumerate(nums):
            self._update_tree(i + 1, v)
    
    def _update_tree(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # move to parent
    
    def _prefix_sum(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # move to responsible range
        return total
    
    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        self._update_tree(index + 1, delta)
    
    def sumRange(self, left: int, right: int) -> int:
        return self._prefix_sum(right + 1) - self._prefix_sum(left)

Dry Run​

nums = [1,3,5], BIT (1-indexed): tree = [0,1,4,5,0...]

  • sumRange(0,2) = prefix(3) - prefix(0) = 9 - 0 = 9 ✓
  • update(1,2): delta = 2-3 = -1 → propagate tree updates
  • sumRange(0,2) = 8 ✓

Why BIT Over Segment Tree?​

BIT is simpler to code and has a smaller constant factor. Use Segment Tree when you need range updates or more complex queries (min, max, GCD).

Complexity​

  • Time: O(log n) per update and query
  • Space: O(n)

Key Terms​

TermDefinition
Binary Indexed Tree (Fenwick Tree)A compact array-based structure storing partial sums, where each index is responsible for a range determined by its lowest set bit.
i & (-i)Isolates the lowest set bit of i, giving the size of the range that index i covers.
Prefix sumSum of all elements from index 0 up to a given index; the BIT computes this in O(log n).
Point update, range queryThe BIT's core operation pair: change one element, query a running range sum, both in O(log n).
Segment TreeAlternative structure supporting the same operations plus range updates and other range queries (min/max/GCD) at slightly higher constant cost.

FAQ​

  1. Why not just use a prefix sum array like in LC 304? A plain prefix sum array gives O(1) query but O(n) update (every subsequent prefix must shift), which is too slow here since updates are frequent.
  2. Can this be solved without extra space? No — the BIT itself is the O(n) auxiliary structure that makes O(log n) update and query possible; you can't avoid keeping some structure alongside nums.
  3. What if left > right or indices are out of bounds in sumRange? Production code should validate bounds before calling _prefix_sum; the reference solution assumes valid LeetCode-constrained input.
  4. How would this change if range updates (not just point updates) were required? Switch to a Segment Tree with lazy propagation, or a BIT variant using two Fenwick trees to support range-update/range-query.
  5. What's the follow-up interviewers usually ask? "Implement the same with a Segment Tree" or "extend to support range min/max query," which BIT cannot do as naturally as a Segment Tree.

Quick Revision​

  • Pattern: Binary Indexed Tree (Fenwick Tree) for online point-update, range-sum queries.
  • BIT is 1-indexed internally; map array index i to tree index i+1.
  • _update_tree: add delta to tree[i], then move to next responsible index via i += i & (-i).
  • _prefix_sum: accumulate tree[i], then move down via i -= i & (-i).
  • sumRange(l, r) = prefix_sum(r+1) - prefix_sum(l).
  • update(index, val): compute delta = val - old_value, then propagate delta through the tree.
  • Both operations run in O(log n) because at most O(log n) bits change per index walk.
  • Prefer BIT over Segment Tree when you only need sum queries — simpler code, smaller constant.
  • 304-RangeSumQuery2D-Immutable — immutable 2D analogue solved with prefix sums instead of a BIT.
  • LC 308 - Range Sum Query 2D - Mutable (2D BIT extension; not in this directory).
  • Segment Tree range-query/range-update problems share the same "point/range update with fast aggregate query" pattern.