How do you approach Range Sum Query - Mutable?

A prefix-sum array makes sumRange O(1) but update O(n) - too slow for many updates.

What is the time complexity of Range Sum Query - Mutable?

Time complexity: O((n + q) log n) where q is the number of operations. Space complexity: O(n).

What are common mistakes on Range Sum Query - Mutable?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Range Sum Query - Mutable

HardData Structures

Description

Given an integer array nums, build a structure supporting two operations:

update(index, val) - replace nums[index] with val.
sumRange(left, right) - return the sum of nums[left..right] inclusive.

To keep the harness simple, you implement a single function processOperations(nums, operations) where each operation is either ["update", index, val] or ["sum", left, right]. Return an array containing the result of each "sum" operation in order ("update" operations contribute nothing to the output).

Both update and sumRange must run in better than O(n) per call - the intended complexity is O(log n) each.

Example 1

Input: nums = [1,3,5], operations = [["sum",0,2],["update",1,2],["sum",0,2]]

Output: [9,8]

Explanation: First sum is 1+3+5=9. After updating index 1 to 2, the array is [1,2,5] and the second sum is 1+2+5=8.

Constraints

- 1 <= nums.length <= 3 * 10^4 - -100 <= nums[i] <= 100 - 0 <= index < nums.length - -100 <= val <= 100 - 0 <= left <= right < nums.length - 1 <= operations.length <= 3 * 10^4

Range Sum Query - Mutable: approach, complexity and pitfalls

A hard design problem, graded against 5 test cases (2 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

A prefix-sum array makes sumRange O(1) but update O(n) - too slow for many updates.
Use a segment tree (or Fenwick / BIT). Each node stores the sum of a range; updates and queries traverse O(log n) nodes.
For a Fenwick tree, sumRange(l, r) = prefix(r) - prefix(l-1).

The optimal approach

Show the approach: Fenwick Tree (Binary Indexed Tree)

A Fenwick tree supports both point updates and prefix sums in O(log n). To handle replacement updates we track the current value of each index and apply the delta (`new - old`) to the BIT. `sumRange(l, r) = prefix(r) - prefix(l-1)`.

A segment tree is the more general solution and is required if we ever need range-update + range-query (with lazy propagation). For sum-only point-update + range-query, BIT is leaner.

Time: O((n + q) log n) where q is the number of operations
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.