Range Sum Query - Mutable
Last Updated: April 4, 2026
Understanding the Problem
We need a data structure that supports two operations on an array: point updates (change one element) and range sum queries (sum a contiguous subarray). The catch is that both operations are interleaved, so we can't just precompute all answers upfront.
If updates never happened, a prefix sum array would give us O(1) range queries after O(n) preprocessing. But every time we update a single element, the prefix sum becomes stale, and rebuilding it costs O(n). On the flip side, if queries never happened, we'd just store the array and update in O(1). The problem forces us to handle both efficiently, and that tension between fast updates and fast queries is what makes this interesting.
The key insight is that we need a data structure that can decompose range operations into smaller pieces, updating only the relevant pieces when an element changes. Both Segment Trees and Binary Indexed Trees (Fenwick Trees) achieve this by splitting the array into hierarchical segments.
Key Constraints:
1 <= nums.length <= 3 * 10^4→ With n up to 30,000, an O(n) per operation approach gives 30,000 30,000 = 9 10^8 operations in the worst case. That's too slow. We need something better than linear per operation.- At most
3 * 10^4calls toupdateandsumRange→ Combined with n up to 30,000, the total work budget is roughly 30,000 operations. If each operation is O(log n), that's about 30,000 * 15 = 450,000 operations total, which is very comfortable. -100 <= nums[i] <= 100→ Small values, no overflow concerns with 32-bit integers for sums.
Approach 1: Brute Force (Prefix Sum with Rebuild)
Intuition
The most natural first thought: use a prefix sum array to answer range queries in O(1). When an update happens, just rebuild the prefix sum from the changed index onward.
For sumRange(left, right), the answer is prefix[right + 1] - prefix[left]. For update(index, val), we update the original array, then recompute the prefix sums from index to the end.
This is a perfectly reasonable starting point, and for small arrays with few updates, it works fine.
Algorithm
- During initialization, build a prefix sum array where
prefix[i]= sum ofnums[0..i-1]. - For
sumRange(left, right), returnprefix[right + 1] - prefix[left]. - For
update(index, val), compute the differencedelta = val - nums[index], updatenums[index] = val, then adddeltato every prefix sum fromprefix[index + 1]throughprefix[n].
Example Walkthrough
Code
- Time Complexity: O(n) per
update, O(1) persumRange, O(n) for initialization. Each update potentially modifies every prefix sum from the changed index to the end, which is O(n) in the worst case. Queries are O(1) thanks to the prefix sum formula. - Space Complexity: O(n). We store the prefix sum array of size n + 1 alongside the original array.
Every update call walks through the prefix array from the changed index to the end. What if we could decompose the array into smaller segments, so that updating one element only affects a few segments?
Approach 2: Square Root Decomposition
Intuition
Instead of maintaining one giant prefix sum, split the array into blocks of size roughly sqrt(n). Each block stores its own precomputed sum. When we update an element, we only need to adjust the sum for that one block, which is O(1). When we query a range, we sum up the complete blocks in the middle and manually add the partial blocks at the edges.
This gives us O(1) updates and O(sqrt(n)) queries. Both operations are sub-linear, which is a big improvement over the brute force.
Algorithm
- Choose a block size
b = floor(sqrt(n)). - Create an array
blockSumwhereblockSum[k]= sum of elements in block k. - For
update(index, val): compute which block the index belongs to (index / b), update the original array, and adjust the block sum by the difference. - For
sumRange(left, right): add up partial elements in the first and last blocks, then add complete block sums for all blocks fully contained in the range.
Example Walkthrough
Code
- Time Complexity: O(1) per
update, O(sqrt(n)) persumRange, O(n) for initialization. Update changes one element and one block sum. Query iterates over at most O(sqrt(n)) blocks and O(sqrt(n)) individual elements in edge blocks. - Space Complexity: O(sqrt(n)). We store the block sum array of size ceil(n / sqrt(n)), plus the original array.
Each query still iterates through up to O(sqrt(n)) elements. What if we used a tree-based decomposition where each level halves the range, giving O(log n) per operation?
Approach 3: Binary Indexed Tree (Fenwick Tree)
Intuition
A Binary Indexed Tree (BIT), also called a Fenwick Tree, uses the binary representation of indices to achieve O(log n) for both updates and prefix sum queries. Each position i in the BIT stores the sum of a specific range of elements, determined by the lowest set bit of i.
For index 6 (binary 110), the lowest set bit is 2, so BIT[6] stores the sum of 2 elements. For index 8 (binary 1000), the lowest set bit is 8, so BIT[8] stores the sum of 8 elements. To get a prefix sum, you hop through at most log(n) positions. To update, you propagate the change to at most log(n) ancestors.
To answer sumRange(left, right), we compute prefixSum(right) - prefixSum(left - 1).
Algorithm
- Create a BIT array of size n + 1 (1-indexed).
- Initialize it by inserting each element one by one using the update operation.
- For
update(index, val): computedelta = val - nums[index], updatenums[index], then propagatedeltaup through the BIT by repeatedly adding the lowest set bit to the index. - For
sumRange(left, right): computequery(right + 1) - query(left), wherequery(i)sums BIT values by repeatedly stripping the lowest set bit from i.
Example Walkthrough
Code
- Time Complexity: O(log n) per
update, O(log n) persumRange, O(n log n) for initialization. Each update propagates through at most log(n) positions. Each query hops through at most log(n) positions. Initialization calls update n times, each O(log n). - Space Complexity: O(n). The BIT array has n + 1 elements.
The Fenwick Tree is already O(log n), but it only supports sum queries. For a more general structure that can handle range min/max or lazy propagation, we can use a Segment Tree.
Approach 4: Segment Tree
Intuition
A Segment Tree builds a complete binary tree where each node stores the sum of a contiguous range. The root stores the total sum, its two children store sums of the left and right halves, and so on recursively until each leaf holds a single element.
For updates, we change the leaf and walk up to the root, recalculating each ancestor's sum. For queries, if the query range fully covers a node's range, we return that node's value. Otherwise, we recurse into the children that overlap with the query range.
Every range [left, right] can be decomposed into at most O(log n) node ranges in the tree. At each level, at most two nodes have partial overlap with the query range. All nodes between them are fully contained and returned immediately. This limits total nodes visited to O(log n).
For updates, changing a leaf only affects the O(log n) ancestors on the path from that leaf to the root. Each ancestor recalculates its sum from its two children.
Algorithm
- Build a segment tree array of size 4n (to account for the tree structure).
- Recursively build the tree: each leaf holds one array element, each internal node holds the sum of its children.
- For
update(index, val): find the leaf for that index, update it, then propagate the change up to the root by recalculating parent sums. - For
sumRange(left, right): recursively query the tree, combining results from nodes whose ranges overlap with [left, right].
Example Walkthrough
Code
- Time Complexity: O(log n) per
update, O(log n) persumRange, O(n) for initialization. Build visits every node once (2n - 1 nodes), which is O(n). Both update and query traverse at most O(log n) levels of the tree. - Space Complexity: O(n). The segment tree array has 4n elements, the standard safe upper bound for array-based segment trees.