Log inSign up
mediumLeetCodeNot Started

Range Sum Query - Mutable

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

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

1. Update: void update(int index, int val) updates the value of nums[index] to be val. 2. Sum Range: int sumRange(int left, int right) returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Both operations should execute efficiently in O(log n) time using a Binary Indexed Tree (Fenwick Tree) or Segment Tree.

Example 1 · Example 1:

Input: ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output: [null, 9, null, 8]
Explanation: NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1, 2, 5] numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Example 2 · Example 2:

Input: ["NumArray", "sumRange", "update", "sumRange"] [[[7, 2, 7, 2, 0]], [0, 2], [4, 6], [0, 4]]
Output: [null, 16, null, 24]
Explanation: Initial sum [0..2] = 7+2+7=16. After setting index 4 to 6, sum [0..4] = 7+2+7+2+6=24.

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i], val <= 100
  • 0 <= index < nums.length
  • 0 <= left <= right < nums.length
  • At most 3 * 104 calls will be made to update and sumRange.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Range Sum Query - Mutable.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Range Sum Query - Mutable
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Basic prototyping when sum queries are very rare.
  • BETTER: When simplicity and O(1) update time is desired.
  • OPTIMAL: The universally preferred industry standard for dynamic point update range sum queries.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Direct Array Storage

Intuition

Maintain the elements in a plain array: - update(index, val): Directly set nums[index] = val in O(1) time. - sumRange(left, right): Loop i from left to right accumulating the sum in O(n) time. With up to 30,000 operations, total runtime reaches O(Q \cdot n) ≈ 9 × 108 operations, leading to Time Limit Exceeded.

When to apply: Basic prototyping when sum queries are very rare.

Algorithm

  1. Step 1: Store input array in nums.
  2. Step 2: On update(index, val), set nums[index] = val.
  3. Step 3: On sumRange(left, right), loop i from left to right summing nums[i] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class NumArrayBrute {
5 std::vector<int> nums;
6public:
7 NumArrayBrute(std::vector<int>& arr) : nums(arr) {}
8
9 void update(int index, int val) {
10 nums[index] = val;
11 }
12
13 int sumRange(int left, int right) {
14 int sum = 0;
15 for (int i = left; i <= right; ++i) sum += nums[i];
16 return sum;
17 }
18};
19
20int main() {
21 std::vector<int> nums = {1, 3, 5};
22 NumArrayBrute na(nums);
23 std::cout << na.sumRange(0, 2) << std::endl;
24 na.update(1, 2);
25 std::cout << na.sumRange(0, 2) << std::endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(1) for update, O(n) for sumRange
  • Space complexity: O(n) auxiliary space

2. Square Root Decomposition

Intuition

Divide nums into blocks of size B = \lceil \sqrt{n} \rceil. Maintain a blocks array where blocks[b] stores the sum of all elements in block b: - update(index, val): 1. Determine block b = index / B. 2. Update block sum: \text{blocks}[b] += val - nums[index]. 3. Set nums[index] = val. Runs in O(1) time! - sumRange(left, right): 1. Sum individual boundary elements in the partial starting and ending blocks. 2. For fully covered middle blocks, add precomputed \text{blocks}[b]. Runs in O(\sqrt{n}) time! Fast and simple to implement without complex tree structures.

When to apply: When simplicity and O(1) update time is desired.

Algorithm

  1. Step 1: Set block size B = ceil(sqrt(n)) and compute block sums.
  2. Step 2: On update(index, val), adjust block sum by (val - nums[index]) and update nums[index] in O(1).
  3. Step 3: On sumRange(left, right), sum boundary elements and add full block sums in O(sqrt(n)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4
5class NumArraySqrt {
6 int n, b;
7 std::vector<int> nums;
8 std::vector<int> blocks;
9public:
10 NumArraySqrt(std::vector<int>& arr) : n(arr.size()), nums(arr) {
11 b = std::max(1, (int)std::sqrt(n));
12 blocks.assign((n + b - 1) / b, 0);
13 for (int i = 0; i < n; ++i) {
14 blocks[i / b] += nums[i];
15 }
16 }
17
18 void update(int index, int val) {
19 int blockIdx = index / b;
20 blocks[blockIdx] += val - nums[index];
21 nums[index] = val;
22 }
23
24 int sumRange(int left, int right) {
25 int sum = 0;
26 int startBlock = left / b;
27 int endBlock = right / b;
28
29 if (startBlock == endBlock) {
30 for (int i = left; i <= right; ++i) sum += nums[i];
31 } else {
32 for (int i = left; i < (startBlock + 1) * b; ++i) sum += nums[i];
33 for (int block = startBlock + 1; block < endBlock; ++block) sum += blocks[block];
34 for (int i = endBlock * b; i <= right; ++i) sum += nums[i];
35 }
36 return sum;
37 }
38};
39
40int main() {
41 std::vector<int> nums = {1, 3, 5};
42 NumArraySqrt na(nums);
43 std::cout << na.sumRange(0, 2) << std::endl;
44 na.update(1, 2);
45 std::cout << na.sumRange(0, 2) << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(1) for update, O(sqrt(n)) for sumRange
  • Space complexity: O(sqrt(n)) auxiliary space for block sums

3. Binary Indexed Tree (Fenwick Tree)

Intuition

A Binary Indexed Tree (Fenwick Tree) is the most cache-friendly and elegant choice for point-update prefix/range-sum queries: 1. Internally store tree[1...n] and keep a copy of nums[0...n-1] to compute deltas: - When update(index, val) is called: - Compute \delta = val - nums[index]. - Set nums[index] = val. - Propagate \delta through the tree at 1-based index i = index + 1 using i += i \mathrel{\&} -i. Runs in O(log n). - When sumRange(left, right) is called: - Return \text{query}(right + 1) - \text{query}(left). - Prefix query computes sum by stepping down i -= i \mathrel{\&} -i. Runs in O(log n). 2. Construction is completed in O(n) time.

When to apply: The universally preferred industry standard for dynamic point update range sum queries.

Algorithm

  1. Step 1: Allocate tree array of size n + 1 and copy nums.
  2. Step 2: Linear construction of BIT in O(n) time.
  3. Step 3: On update(index, val), delta = val - nums[index], nums[index] = val, add delta to BIT at index + 1 in O(log n).
  4. Step 4: On sumRange(left, right), return query(right + 1) - query(left) in O(log n).

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
NumArray initialized with nums = [1, 3, 5]
Visual state
Values and pointers at this exact step
pointers
S
1
3
5
0
1
2
Check / comparison
nums = [1, 3, 5], prefix sums = [1, 4, 9]
Decision / next transition
Ready to process queries
Why this step matters

NumArray initialized with nums = [1, 3, 5]. Fenwick tree built in O(n) time.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class NumArray {
5 int n;
6 std::vector<int> nums;
7 std::vector<int> tree;
8
9 void add(int idx, int delta) {
10 for (; idx <= n; idx += idx & -idx) {
11 tree[idx] += delta;
12 }
13 }
14
15 int query(int idx) {
16 int sum = 0;
17 for (; idx > 0; idx -= idx & -idx) {
18 sum += tree[idx];
19 }
20 return sum;
21 }
22
23public:
24 NumArray(std::vector<int>& arr) : n(arr.size()), nums(arr), tree(arr.size() + 1, 0) {
25 for (int i = 0; i < n; ++i) tree[i + 1] = nums[i];
26 for (int i = 1; i <= n; ++i) {
27 int p = i + (i & -i);
28 if (p <= n) tree[p] += tree[i];
29 }
30 }
31
32 void update(int index, int val) {
33 int delta = val - nums[index];
34 nums[index] = val;
35 add(index + 1, delta);
36 }
37
38 int sumRange(int left, int right) {
39 return query(right + 1) - query(left);
40 }
41};
42
43int main() {
44 std::vector<int> nums = {1, 3, 5};
45 NumArray na(nums);
46 std::cout << na.sumRange(0, 2) << std::endl;
47 na.update(1, 2);
48 std::cout << na.sumRange(0, 2) << std::endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(n) construction, O(log n) for update and sumRange
  • Space complexity: O(n) auxiliary space for the Fenwick tree

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Direct Array StorageO(1) for update, O(n) for sumRangeO(n) auxiliary spaceStore items in an array. update modifies the index in O(1), sumRange sums the subarray in O(n).O(1) for update, O(n) for sumRange
2.Square Root DecompositionO(1) for update, O(sqrt(n)) for sumRangeO(sqrt(n)) auxiliary space for block sumsDivide array into blocks of size B = sqrt(n). Maintain precomputed block sums. update takes O(1), sumRange takes O(sqrt(n)).O(1) for update, O(sqrt(n)) for sumRange
3.Binary Indexed Tree (Fenwick Tree)OptimalO(n) construction, O(log n) for update and sumRangeO(n) auxiliary space for the Fenwick treeMaintain prefix sums using a 1-indexed Fenwick Tree. Both point updates and range queries execute in O(log n) time.O(n) construction, O(log n) for update and sumRange

Common Pitfalls & Crucial Edge Cases

Passing `val` instead of `val - nums[i]` to Fenwick Tree update

Fenwick Tree updates are incremental additions, not value assignments.

Using 0-based indexing without converting to 1-based in Fenwick Tree

Causes infinite loop on index 0.

Forgetting to update the underlying `nums` array

If nums[i] is not updated, subsequent updates to the same index will compute incorrect deltas.

Crucial Edge Cases to Validate:

  • Multiple updates to the same index — Delta must always be calculated against the currently stored value.
  • Query covers single element (L == R) — Returns nums[L].
  • Updating value to 0 or negative numbers — Handled cleanly by signed delta arithmetic.
  • Query covers entire array [0, N - 1] — Returns total sum of all elements.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Discuss the trade-off spectrum: Array (O(1) update, O(N) query) vs Prefix Sum (O(N) update, O(1) query) vs Fenwick/Segment Tree (O(log N) both).
  2. Recommend Fenwick Tree over Segment Tree for implementation speed and 4x lower memory footprint.
  3. Demonstrate clean encapsulation in a NumArray class.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why cannot a standard prefix sum array handle mutable range sum queries efficiently?

2.What time complexity does a Fenwick Tree or Segment Tree provide for both update and sumRange?

3.When updating index i to a new value val in a Fenwick Tree, what delta is passed to the tree?

Back to DSA Sheet