Range Sum Query - Mutable (LeetCode 307)
You get an integer array nums, followed by a mix of two kinds of requests in any order: change one element, or report the sum of a contiguous stretch of elements.
Build the NumArray class:
NumArray(nums)stores the array.update(index, val)setsnums[index]toval.sumRange(left, right)returnsnums[left] + nums[left + 1] + ... + nums[right], both ends included (left <= right).
Worked Examples
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]][null, 9, null, 8][1, 3, 5], so sumRange(0, 2) is 1 + 3 + 5 = 9. update(1, 2) makes it [1, 2, 5], and the next sumRange(0, 2) is 1 + 2 + 5 = 8.⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.lengthAt most
3 * 104calls will be made toupdateandsumRange.
Core Insight
Store in each node the sum of the range it covers, built from its two half-range children: a range sum reads a few whole nodes, and a changed slot sits under only one node per level, so both operations visit O(log N) nodes.
Real-World Scenario & Production Applications
A sales dashboard keeps one number per team and shows the total for any group of neighbouring teams. A team sometimes corrects its number, and the totals must stay right at once. A tree of subtotals does this: a correction repairs the subtotals above that team, and a group total reads a few subtotals instead of adding every team.
Step-by-Step Execution Trace Table
nums = [1, 3, 5] (n = 3). The root is node 0 and covers slots 0..2. Node 1 covers 0..1, node 2 covers 2..2, node 3 covers 0..0 and node 4 covers 1..1.
| Call | Nodes visited | tree[0..4] after | Returns |
|---|---|---|---|
| build | leaves 3, 4 and 2 are filled; node 1 = 1 + 3, node 0 = 4 + 5 | [9, 4, 5, 1, 3] | |
sumRange(0, 2) | node 0 covers 0..2, fully inside the query, so it returns tree[0] | [9, 4, 5, 1, 3] | 9 |
update(1, 2) | 0 → 1 → 4: leaf 4 is set to 2, then node 1 = 1 + 2 = 3, then node 0 = 3 + 5 = 8 | [8, 3, 5, 1, 2] | null |
sumRange(0, 2) | node 0 is fully inside the query, so it returns tree[0] | [8, 3, 5, 1, 2] | 8 |
| 1 | `tree[node]` holds the sum of the slots `left..right` that `node` covers, and its children `2 * node + 1` and `2 * node + 2` hold the two halves, so any range is a few whole nodes and any slot sits under one node per level. |
| 2 | `update` walks to the leaf for `index`, sets it, then recomputes `self.tree[node]` from both children on the way back up; `query` returns the stored sum inside `[ql, qr]`, `0` outside, and the sum of both halves otherwise. |
| 3 | `NumArray`: build `SegmentTree(nums)`, `update(index, val)` calls the tree's `update`, `sumRange(left, right)` returns `self.seg.query(left, right)`. |
| 4 | The trap: after the recursive `update` returns, recompute `self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]`, or every sum above the leaf stays stale. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A plain array changes one element in but sums a range in . A prefix-sum array sums any range in but needs an rebuild after every change. A segment tree stores the sum of many ranges in a binary tree. Node node covers the slots left..right, and its two children cover the two halves. A range sum then reads a few stored nodes, and a change repairs one path from a leaf to the root. Both take .
🏟️ The Analogy: Team Totals in a Company
A company reports sales by team. Each manager keeps the total of the two groups directly below, and the head of the company keeps the grand total. To total the sales of a stretch of neighbouring teams, you read the totals of a few managers whose groups lie completely inside that stretch. When one team corrects its number, only the managers above that team, up to the head, recompute their totals.
🔑 Why It Works
After every update, self.tree[node] equals the sum of the slots left..right that node covers: update sets the leaf, then recomputes each ancestor from its two children on the way back up. query returns a stored sum only for a node fully inside [ql, qr], returns 0 for a node fully outside, and adds both children otherwise. At most two nodes per level overlap only part of the range, so every call visits nodes.
Not recomputing ancestors: changing only the leaf in
updateleaves every sum above it stale; on LeetCode Example 1 (nums = [1,3,5], thenupdate(1, 2)) the secondsumRange(0, 2)returns 9 instead of 8. Recomputeself.tree[node]after the recursive call returns.An overlap test instead of a containment test:
querymay returnself.tree[node]only whenql <= left and right <= qr; a node that merely overlaps the range also holds slots outside it, andsumRange(0, 1)on[1,3,5]would return 9 instead of 4.Adding
valto the leaf:update(index, val)replaces the value, so the leaf is set toval. With+=, the secondsumRange(0, 2)in Example 1 returns 11 instead of 8.Too little space:
2 * nslots overflow whennis not a power of two; allocate4 * n.Rebuilding the whole tree on every update: correct, but each call then costs
O(N); with3 * 104calls on3 * 104elements that is about 10^9 steps.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Change one element" mixed with "sum of a contiguous stretch", many times and in any order: a prefix array rebuilds in O(N) per change, and a plain array sums in O(N). Point updates plus range sums fit a Fenwick tree or a segment tree. The segment tree is the one to know when a node must store more than a prefix difference can give, such as a maximum.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
self.tree[node] always equals the sum of the slots left..right that node covers; update keeps it true by recomputing each ancestor from its two children, and query returns a stored sum only when ql <= left and right <= qr.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Segment Tree, because I need point updates and range sums mixed together. Each node stores the sum of the slots it covers, and its two children cover the two halves. A range sum returns a stored sum for a node fully inside the range, zero for a node fully outside, and adds both children for a node that overlaps only part of the range. At most two nodes per level overlap only part of the range, so a query is
O(log N). An update walks to the one leaf for the index and sets it. On the way back up it recomputes every ancestor from its two children, and that line is the trap: without it, later queries read old sums. I allocate four times N nodes, because two times N can overflow when N is not a power of two. Building costsO(N)and space isO(N). If the problem only adds to one position and sums a prefix, I would use a Fenwick tree instead, because it is shorter.
Complexity & Mathematical Proof
O(N) build, O(log N) update & query
Look at update: it follows one path from the root to a leaf, and each call halves the range, so the depth is about log2(N) + 1. It does O(1) work per node on the way back up: O(log N). Look at query: a node fully inside or fully outside the range returns at once. At most two nodes per level overlap only part of the range, so the calls per level stay at most four and the total is O(log N). _build visits each of the about 2N nodes once and does O(1) work per node: O(N). NumArray.update is one tree update and sumRange is one tree query.
O(N)
self.tree has 4 * N slots: O(N). The recursion is at most about log2(N) + 1 calls deep, which is O(log N) of call stack.
T(update) = T(query) = O(log N); build = O(N)
Derivation Progression
about 2N nodes × O(1) = O(N)
_build fills each leaf once and combines each inner node once.
depth × O(1) = O(log N)
One path down to the leaf, one recompute per ancestor on the way up.
at most 4 calls per level × O(log N) levels = O(log N)
Only nodes that overlap part of the range split; at most two per level do.
Variable Definitions
Length of nums
A tree slot; its children are 2 * node + 1 and 2 * node + 2
The slots of nums that node covers
Memory Architecture & Bounds
O(log N): the recursion is one call per level
O(N): tree has 4N slots
O(1) per call
Boundary Best / Worst Cases
for a query whose range is exactly the whole array: the root is fully inside
per operation; to build
per operation
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "change one element", "sum of a contiguous stretch", "in any order". Point updates mixed with range sums: a Segment Tree whose node stores the sum of its range (a range sum reads a few whole nodes, an update repairs one path).
values in and at most calls. Sums stay within . Naive: up to steps; segment tree: about node visits, since the tree is about 16 levels deep.
In a concurrent service, an update rewrites one node per level from the leaf to the root. A reader that runs between two of those writes adds a new leaf to an old ancestor, so guard the walk with a lock, or build the changed path as new nodes and swap the root in one step.
Range Sum Query - Mutable (LeetCode 307)
You get an integer array nums, followed by a mix of two kinds of requests in any order: change one element, or report the sum of a contiguous stretch of elements.
Build the NumArray class:
NumArray(nums)stores the array.update(index, val)setsnums[index]toval.sumRange(left, right)returnsnums[left] + nums[left + 1] + ... + nums[right], both ends included (left <= right).
Worked Examples
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]][null, 9, null, 8][1, 3, 5], so sumRange(0, 2) is 1 + 3 + 5 = 9. update(1, 2) makes it [1, 2, 5], and the next sumRange(0, 2) is 1 + 2 + 5 = 8.⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.lengthAt most
3 * 104calls will be made toupdateandsumRange.
Core Insight
Store in each node the sum of the range it covers, built from its two half-range children: a range sum reads a few whole nodes, and a changed slot sits under only one node per level, so both operations visit O(log N) nodes.
Real-World Scenario & Production Applications
A sales dashboard keeps one number per team and shows the total for any group of neighbouring teams. A team sometimes corrects its number, and the totals must stay right at once. A tree of subtotals does this: a correction repairs the subtotals above that team, and a group total reads a few subtotals instead of adding every team.
Step-by-Step Execution Trace Table
nums = [1, 3, 5] (n = 3). The root is node 0 and covers slots 0..2. Node 1 covers 0..1, node 2 covers 2..2, node 3 covers 0..0 and node 4 covers 1..1.
| Call | Nodes visited | tree[0..4] after | Returns |
|---|---|---|---|
| build | leaves 3, 4 and 2 are filled; node 1 = 1 + 3, node 0 = 4 + 5 | [9, 4, 5, 1, 3] | |
sumRange(0, 2) | node 0 covers 0..2, fully inside the query, so it returns tree[0] | [9, 4, 5, 1, 3] | 9 |
update(1, 2) | 0 → 1 → 4: leaf 4 is set to 2, then node 1 = 1 + 2 = 3, then node 0 = 3 + 5 = 8 | [8, 3, 5, 1, 2] | null |
sumRange(0, 2) | node 0 is fully inside the query, so it returns tree[0] | [8, 3, 5, 1, 2] | 8 |
| 1 | `tree[node]` holds the sum of the slots `left..right` that `node` covers, and its children `2 * node + 1` and `2 * node + 2` hold the two halves, so any range is a few whole nodes and any slot sits under one node per level. |
| 2 | `update` walks to the leaf for `index`, sets it, then recomputes `self.tree[node]` from both children on the way back up; `query` returns the stored sum inside `[ql, qr]`, `0` outside, and the sum of both halves otherwise. |
| 3 | `NumArray`: build `SegmentTree(nums)`, `update(index, val)` calls the tree's `update`, `sumRange(left, right)` returns `self.seg.query(left, right)`. |
| 4 | The trap: after the recursive `update` returns, recompute `self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]`, or every sum above the leaf stays stale. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A plain array changes one element in but sums a range in . A prefix-sum array sums any range in but needs an rebuild after every change. A segment tree stores the sum of many ranges in a binary tree. Node node covers the slots left..right, and its two children cover the two halves. A range sum then reads a few stored nodes, and a change repairs one path from a leaf to the root. Both take .
🏟️ The Analogy: Team Totals in a Company
A company reports sales by team. Each manager keeps the total of the two groups directly below, and the head of the company keeps the grand total. To total the sales of a stretch of neighbouring teams, you read the totals of a few managers whose groups lie completely inside that stretch. When one team corrects its number, only the managers above that team, up to the head, recompute their totals.
🔑 Why It Works
After every update, self.tree[node] equals the sum of the slots left..right that node covers: update sets the leaf, then recomputes each ancestor from its two children on the way back up. query returns a stored sum only for a node fully inside [ql, qr], returns 0 for a node fully outside, and adds both children otherwise. At most two nodes per level overlap only part of the range, so every call visits nodes.
Not recomputing ancestors: changing only the leaf in
updateleaves every sum above it stale; on LeetCode Example 1 (nums = [1,3,5], thenupdate(1, 2)) the secondsumRange(0, 2)returns 9 instead of 8. Recomputeself.tree[node]after the recursive call returns.An overlap test instead of a containment test:
querymay returnself.tree[node]only whenql <= left and right <= qr; a node that merely overlaps the range also holds slots outside it, andsumRange(0, 1)on[1,3,5]would return 9 instead of 4.Adding
valto the leaf:update(index, val)replaces the value, so the leaf is set toval. With+=, the secondsumRange(0, 2)in Example 1 returns 11 instead of 8.Too little space:
2 * nslots overflow whennis not a power of two; allocate4 * n.Rebuilding the whole tree on every update: correct, but each call then costs
O(N); with3 * 104calls on3 * 104elements that is about 10^9 steps.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Change one element" mixed with "sum of a contiguous stretch", many times and in any order: a prefix array rebuilds in O(N) per change, and a plain array sums in O(N). Point updates plus range sums fit a Fenwick tree or a segment tree. The segment tree is the one to know when a node must store more than a prefix difference can give, such as a maximum.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
self.tree[node] always equals the sum of the slots left..right that node covers; update keeps it true by recomputing each ancestor from its two children, and query returns a stored sum only when ql <= left and right <= qr.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Segment Tree, because I need point updates and range sums mixed together. Each node stores the sum of the slots it covers, and its two children cover the two halves. A range sum returns a stored sum for a node fully inside the range, zero for a node fully outside, and adds both children for a node that overlaps only part of the range. At most two nodes per level overlap only part of the range, so a query is
O(log N). An update walks to the one leaf for the index and sets it. On the way back up it recomputes every ancestor from its two children, and that line is the trap: without it, later queries read old sums. I allocate four times N nodes, because two times N can overflow when N is not a power of two. Building costsO(N)and space isO(N). If the problem only adds to one position and sums a prefix, I would use a Fenwick tree instead, because it is shorter.
Complexity & Mathematical Proof
O(N) build, O(log N) update & query
Look at update: it follows one path from the root to a leaf, and each call halves the range, so the depth is about log2(N) + 1. It does O(1) work per node on the way back up: O(log N). Look at query: a node fully inside or fully outside the range returns at once. At most two nodes per level overlap only part of the range, so the calls per level stay at most four and the total is O(log N). _build visits each of the about 2N nodes once and does O(1) work per node: O(N). NumArray.update is one tree update and sumRange is one tree query.
O(N)
self.tree has 4 * N slots: O(N). The recursion is at most about log2(N) + 1 calls deep, which is O(log N) of call stack.
T(update) = T(query) = O(log N); build = O(N)
Derivation Progression
about 2N nodes × O(1) = O(N)
_build fills each leaf once and combines each inner node once.
depth × O(1) = O(log N)
One path down to the leaf, one recompute per ancestor on the way up.
at most 4 calls per level × O(log N) levels = O(log N)
Only nodes that overlap part of the range split; at most two per level do.
Variable Definitions
Length of nums
A tree slot; its children are 2 * node + 1 and 2 * node + 2
The slots of nums that node covers
Memory Architecture & Bounds
O(log N): the recursion is one call per level
O(N): tree has 4N slots
O(1) per call
Boundary Best / Worst Cases
for a query whose range is exactly the whole array: the root is fully inside
per operation; to build
per operation
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "change one element", "sum of a contiguous stretch", "in any order". Point updates mixed with range sums: a Segment Tree whose node stores the sum of its range (a range sum reads a few whole nodes, an update repairs one path).
values in and at most calls. Sums stay within . Naive: up to steps; segment tree: about node visits, since the tree is about 16 levels deep.
In a concurrent service, an update rewrites one node per level from the leaf to the root. A reader that runs between two of those writes adds a new leaf to an old ancestor, so guard the walk with a lock, or build the changed path as new nodes and swap the root in one step.