{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Range Sum Query - Mutable – Solution & Complexity

Interview solutions
/
Range Sum Query - Mutable

Solution Walkthrough

1. Why a plain prefix array is not enough

  • With no updates, prefix sums answer every range query in O(1).
  • But after setting one position to a new value, every prefix sum after that index changes, so a plain prefix array makes updates O(n).

2. Brute-force baseline

  • You can perform updates directly in nums and answer each sumRange by looping from left to right.
  • That costs O(n) per query and is too slow when both the array and the operation list are large.

3. Store partial sums in a Fenwick tree

  • A Fenwick tree stores carefully chosen prefix fragments so one point update touches only O(log n) tree slots.
  • A prefix query also touches only O(log n) slots, and an inclusive range sum becomes prefix(right) - prefix(left - 1).
  • Keep a copy of nums so you can compute the delta when an update overwrites an old value.

4. Final solution (all languages)

Fenwick-tree partial sums give logarithmic updates and queries with compact code.

def range_sum_query_mutable(nums: list[int], operations: list[str], first: list[int], second: list[int]) -> list[int]:
    bit = [0] * (len(nums) + 1)

    def add(index: int, delta: int) -> None:
        index += 1
        while index < len(bit):
            bit[index] += delta
            index += index & -index

    def prefix_sum(index: int) -> int:
        total = 0
        index += 1
        while index > 0:
            total += bit[index]
            index -= index & -index
        return total

    for index, value in enumerate(nums):
        add(index, value)

    answer = []
    for operation, a, b in zip(operations, first, second):
        if operation == "update":
            delta = b - nums[a]
            nums[a] = b
            add(a, delta)
        else:
            answer.append(prefix_sum(b) - (prefix_sum(a - 1) if a > 0 else 0))

    return answer

5. Implementation notes

  • The Fenwick tree uses 1-based indexing internally even though the problem uses 0-based array indices.
  • update overwrites a value, so you must add the difference (new - old) instead of the new value itself.
  • A segment tree solves the same interface and extends more naturally to range updates or different associative operations.

FAQ

See also

Practice Range Sum Query - Mutable online (run code in the browser)Design Add and Search Words solution (medium)Find Median from Data Stream solution (hard)Implement Trie solution (medium)LRU Cache solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?