Range Sum Query - Mutable

Range Sum Query - Mutable

What is this problem about?

The Range Sum Query - Mutable problem extends the immutable version by supporting point updates. After changing arr[index] = val, subsequent range sum queries must reflect the update. This requires a dynamic structure like a Binary Indexed Tree or segment tree. The array, design, binary indexed tree, and segment tree interview pattern is the core.

Why is this asked in interviews?

Microsoft, TikTok, Google, Bloomberg, and Adobe ask this as the standard BIT (Fenwick Tree) problem. It validates understanding of the BIT — a fundamental data structure that supports O(log n) point updates and O(log n) range sum queries.

Algorithmic pattern used

Binary Indexed Tree (Fenwick Tree). Build BIT from initial array. update(i, delta): traverse from i upward using i += i & (-i), add delta at each step. query(i) = prefix sum from 1 to i: traverse from i downward using i -= i & (-i), sum values. sumRange(l, r): query(r+1) - query(l).

Example explanation

arr=[1,3,5]. Build BIT. sumRange(0,2) = query(3)-query(0) = 1+3+5 = 9. update(1,2): change arr[1] from 3 to 2. BIT update: delta = 2-3 = -1. sumRange(0,2) = 8.

Common mistakes candidates make

• Using 0-indexed BIT (BIT is 1-indexed internally).
• Update: i += i & (-i) (upward propagation for update, downward for query).
• Swapping update and query traversal directions.
• Not converting between 0-indexed array and 1-indexed BIT.

Interview preparation tip

The BIT update and query traversal directions are opposites: update goes UP (i += i & (-i)) and prefix sum query goes DOWN (i -= i & (-i)). Memorize these two loops cold. BIT is the most space-efficient dynamic range query structure — O(n) space, O(log n) operations. After mastering 1D BIT, extend to 2D BIT for matrix range sum problems.