Range Sum Query - Mutable
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 O(1) range queries after O(n) preprocessing. But every time we change a single element, the prefix sum becomes stale, and rebuilding it costs O(n). If queries never happened, we could store the array and update in O(1). The problem forces both to be efficient, and that tension between fast updates and fast queries is what shapes the solution.
A data structure that decomposes range operations into smaller pieces solves this: when one element changes, only the few pieces that contain it need to be touched. Both Segment Trees and Binary Indexed Trees (Fenwick Trees) work this way, splitting the array into hierarchical segments.
Key Constraints:
1 <= nums.length <= 3 * 10^4and at most3 * 10^4operations → An O(n) per operation approach costs up to 3 10^4 3 10^4 = 9 10^8 element touches, which is too slow. We need sub-linear cost per operation, ideally O(log n).-100 <= nums[i] <= 100→ With at most 3 10^4 elements, the largest possible sum is 3 10^4 100 = 3 10^6, well within 32-bit integer range. No overflow concerns.
Approach 1: Brute Force (Prefix Sum with Rebuild)
Intuition
Use a prefix sum array to answer range queries in O(1), and rebuild the affected portion of it whenever an element changes. For sumRange(left, right), the answer is prefix[right + 1] - prefix[left]. For update(index, val), change the original array, then recompute the prefix sums from index to the end.
This is a good baseline. It keeps queries fast but pays the full O(n) rebuild cost on every update.
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, which is O(n). The next approach decomposes the array into blocks so that an update touches only one block.
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 O(1) updates and O(sqrt(n)) queries. Both operations are sub-linear, so neither degrades to O(n) the way the brute-force update does.
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)) blocks and edge elements. A tree-based decomposition, where each level halves the range, brings both operations down to O(log n).
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 (1-indexed) stores the sum of a block of elements ending at i, and the block length is 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 (positions 5 and 6). For index 8 (binary 1000), the lowest set bit is 8, so BIT[8] stores the sum of 8 elements (positions 1 through 8). A prefix sum is assembled by stripping off the lowest set bit repeatedly, visiting at most log(n) positions. An update adds the delta to every BIT position responsible for that element, found by adding the lowest set bit repeatedly, again at most log(n) positions.
To answer sumRange(left, right), compute prefixSum(right) - prefixSum(left - 1), where prefixSum(k) is the sum of nums[0..k].
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) - query(left - 1), wherequery(i)returns the sum ofnums[0..i]by adding BIT values while repeatedly stripping the lowest set bit. Whenleftis 0, the second term is 0.
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 reaches O(log n) for both operations, but it relies on the fact that range sums can be split into prefix differences. A Segment Tree stores an explicit value per range and handles operations that have no inverse, such as range minimum or maximum, as well as lazy propagation for range updates.
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] decomposes into at most O(log n) node ranges. At each level of the tree, at most two nodes partially overlap the query range; the query recurses only into those. Every other relevant node is fully contained and returned without further recursion. Two partial nodes per level across log(n) levels bounds the visited nodes at O(log n).
For updates, changing a leaf affects only the ancestors on the path from that leaf to the root, which is O(log n) nodes. Each ancestor recomputes its sum from its two children, so every stored sum stays consistent.
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.