Range Sum Query - Mutable (LeetCode 307)
You will see how a segment tree answers range sums and point updates in O(log N) by storing the sum of every half-range.
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]⚖️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.
Why It Works & Core Invariant
Store the sum of every range the recursive halving creates: a query range is covered by O(log N) stored nodes, and a changed element only affects the O(log N) nodes on its root path.
Real-World Scenario & Production Applications
Live dashboards and leaderboards that keep running totals while individual values keep changing: bucketed counters (requests per second, sales per day) where a single bucket is corrected and a range total is read on every page load. A plain prefix array would need an O(N) rebuild after every change.
Step-by-Step Execution Trace Table
nums = [1, 3, 5]. Nodes: 0 = [0..2], 1 = [0..1], 2 = [2..2], 3 = [0..0], 4 = [1..1].
| Call | Nodes visited | What happens | tree[0..4] after | Returns |
|---|---|---|---|---|
| build | 3, 4, 1, 2, 0 | leaves 1, 3, 5; node 1 = 1 + 3; node 0 = 4 + 5 | [9, 4, 5, 1, 3] | |
sumRange(0, 2) | 0 | node 0 covers [0..2], fully inside: stored sum | unchanged | 9 |
update(1, 2) | 0 → 1 → 4, back up 1, 0 | leaf 4 = 2; recompute node 1 = 1 + 2 = 3; node 0 = 3 + 5 = 8 | [8, 3, 5, 1, 2] | null |
sumRange(0, 2) | 0 | fully inside again | unchanged | 8 |
| 1 | Every node stores the sum of a range, and its two children store the two halves, so a range is a few stored nodes and a change touches one path. |
| 2 | After every `update`, `self.tree[node]` equals the sum of `nums[left..right]` for its range; `query` returns the stored sum when fully inside, `0` when fully outside, and splits otherwise. |
| 3 | `_build(nums, 0, 0, n - 1)` recursively; `update(index, val)` goes left if `index <= mid` else right, then recomputes; `query(ql, qr)` combines both halves; `NumArray` forwards the calls. |
| 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. |
Target: Range Sum Query - Mutable (LeetCode 307). 4n slots always fit the tree, whatever n is.
Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.
Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A segment tree stores the answer for a range in every node: the root covers the whole array, its two children cover the two halves, and so on down to single elements. Any query range [ql, qr] splits into a few stored nodes (about two per level), and changing one element only touches the nodes on the path from its leaf to the root. Both operations are , and unlike a Fenwick tree the same shape works for max, min or any operation that combines two halves.
🏟️ The Analogy: Regional Sales Reports
A company files sales by store, then by city, then by region, then for the whole country, each report adding up the ones below it. To answer "sales in these twelve neighbouring stores" you pick a couple of city reports that sit fully inside the range plus a few stores at the edges. When one store corrects its number, only its city, its region and the country report need a new total.
🪄 The Mathematical Harmony / Magic Trick
def query(self, ql, qr, node, left, right): if ql <= left and right <= qr: return self.tree[node] # fully inside: stored sum if right < ql or left > qr: return 0 # fully outside: neutral value mid = (left + right) // 2 # partial: ask both halves return self.query(ql, qr, 2 * node + 1, left, mid) + self.query(ql, qr, 2 * node + 2, mid + 1, right) update walks down to the leaf for index, overwrites it with val, and on the way back up sets self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] for every ancestor. That recompute is what keeps every stored sum true.
💡 Summary
Node i covers [left, right], its children 2i + 1 and 2i + 2 cover the halves; 4 * n slots are always enough. Build is , and each update or query is . NumArray passes every call straight through: update sets the value (no difference needed), sumRange is query(left, right).
Not recomputing ancestors: changing only the leaf in
updateleaves every sum above it stale; on[1,3,5],update(1, 2)thensumRange(0, 2)would still return 9. Recomputeself.tree[node]after the recursive call returns.Too little space:
2 * nslots overflow whennis not a power of two; allocate4 * n.Wrong neutral value: a node fully outside the query must return
0for sums (it would be-inffor max,inffor min).Adding instead of overwriting: the segment tree stores values, so
updatesets the leaf toval; addingval(Fenwick style) double-counts the old value.
4-Phase Thought Process Model
You will see how a senior engineer picks a segment tree and explains why updates must recompute on the way up.
Pattern Recognition Signals
The 10-second spot
"Change one element" mixed with "sum of a contiguous stretch", many times and in any order: every call must be fast, not just the reads. A Segment Tree gives O(log N) for both, and the same structure would also handle range max or min if the question changed.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After every update, self.tree[node] equals the sum of nums[left..right] for the range that node covers; query uses a node's stored sum only when the node lies fully inside [ql, qr].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]after the recursiveupdate: changing only the leaf leaves every sum above it stale.self.tree = [0] * (4 * self.n):2 * noverflows whennis not a power of two.return 0for a node fully outside the query: the neutral value for sum.self.tree[node] = valat the leaf: overwrite, don't add.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Segment Tree. Each node stores the sum of a range: the root covers the whole array and each node's two children cover its two halves. For a sum query, a node fully inside the range returns its stored sum, a node fully outside returns zero, and a partly covered node asks both children; that touches about two nodes per level, so
O(log N). For an update, I walk down to the leaf for that index, overwrite it with the new value, and on the way back up recompute each ancestor as the sum of its two children. That recompute is the trap: skip it and every sum above the leaf goes stale. Building the tree isO(N), each update and query isO(log N), and it takesO(N)space with four times n slots.
So: fully inside, fully outside, or split; overwrite the leaf, then recompute every ancestor.
Complexity & Mathematical Proof
O(N) build, O(log N) query & update
Look at the recursion: _build visits each node once, and the tree has 2N - 1 nodes, so build is O(N). update follows one path from the root to a leaf (depth about log2 N) and does O(1) work per node on the way back up: O(log N). query stops at nodes fully inside or fully outside; at each level at most two nodes are partly covered, so it visits O(log N) nodes.
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.
Look at the recursion: _build visits each node once, and the tree has 2N - 1 nodes, so build is O(N). update follows one path from the root to a leaf (depth about log2 N) and does O(1) work per node on the way back up: O(log N). query stops at nodes fully inside or fully outside; at each level at most two nodes are partly covered, so it visits O(log N) nodes.
Derivation Progression
2N - 1 nodes × O(1)
_build creates every leaf and combines every internal node once.
depth × O(1) = O(log N)
One root-to-leaf path down, one recompute per ancestor on the way up.
≤ 2 partial nodes per level = O(log N)
Fully inside or fully outside nodes stop the recursion immediately.
Variable Definitions
Length of nums
A tree slot; its children are 2 * node + 1 and 2 * node + 2
Memory Architecture & Bounds
O(log N): recursion depth of update, query and _build
O(N): self.tree with 4n slots
O(1) per call
Boundary Best / Worst Cases
for a query that covers the whole array (the root answers it)
per operation; to build
per update and query
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "change one element", "sum of a contiguous stretch", "in any order". Updates and range queries interleaved: a Segment Tree (it also covers max/min/other combine operations, where a Fenwick tree does not).
and at most calls: about 16 levels, so each call visits a few dozen nodes. slots is about integers.
Forgetting the recompute leaves stale sums. Recursion depth is only about log2 N, but in a service the array often lives longer than one request: rebuild in O(N) after bulk loads instead of N separate updates.
Core Algorithmic State Invariants
After every `update`, `self.tree[node]` equals the sum of `nums[left..right]` for the range the node covers; children `2 * node + 1` and `2 * node + 2` cover the two halves.
`query` returns the stored sum for a node fully inside `[ql, qr]`, `0` for a node fully outside, and asks both children otherwise; `update` recomputes each ancestor after its child changes.
Build touches 2N - 1 nodes (O(N)); update follows one root-to-leaf path and query at most two partial nodes per level: O(log N) each, with 4n slots of space.
Range Sum Query - Mutable (LeetCode 307)
You will see how a segment tree answers range sums and point updates in O(log N) by storing the sum of every half-range.
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]⚖️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.
Why It Works & Core Invariant
Store the sum of every range the recursive halving creates: a query range is covered by O(log N) stored nodes, and a changed element only affects the O(log N) nodes on its root path.
Real-World Scenario & Production Applications
Live dashboards and leaderboards that keep running totals while individual values keep changing: bucketed counters (requests per second, sales per day) where a single bucket is corrected and a range total is read on every page load. A plain prefix array would need an O(N) rebuild after every change.
Step-by-Step Execution Trace Table
nums = [1, 3, 5]. Nodes: 0 = [0..2], 1 = [0..1], 2 = [2..2], 3 = [0..0], 4 = [1..1].
| Call | Nodes visited | What happens | tree[0..4] after | Returns |
|---|---|---|---|---|
| build | 3, 4, 1, 2, 0 | leaves 1, 3, 5; node 1 = 1 + 3; node 0 = 4 + 5 | [9, 4, 5, 1, 3] | |
sumRange(0, 2) | 0 | node 0 covers [0..2], fully inside: stored sum | unchanged | 9 |
update(1, 2) | 0 → 1 → 4, back up 1, 0 | leaf 4 = 2; recompute node 1 = 1 + 2 = 3; node 0 = 3 + 5 = 8 | [8, 3, 5, 1, 2] | null |
sumRange(0, 2) | 0 | fully inside again | unchanged | 8 |
| 1 | Every node stores the sum of a range, and its two children store the two halves, so a range is a few stored nodes and a change touches one path. |
| 2 | After every `update`, `self.tree[node]` equals the sum of `nums[left..right]` for its range; `query` returns the stored sum when fully inside, `0` when fully outside, and splits otherwise. |
| 3 | `_build(nums, 0, 0, n - 1)` recursively; `update(index, val)` goes left if `index <= mid` else right, then recomputes; `query(ql, qr)` combines both halves; `NumArray` forwards the calls. |
| 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. |
Target: Range Sum Query - Mutable (LeetCode 307). 4n slots always fit the tree, whatever n is.
Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.
Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A segment tree stores the answer for a range in every node: the root covers the whole array, its two children cover the two halves, and so on down to single elements. Any query range [ql, qr] splits into a few stored nodes (about two per level), and changing one element only touches the nodes on the path from its leaf to the root. Both operations are , and unlike a Fenwick tree the same shape works for max, min or any operation that combines two halves.
🏟️ The Analogy: Regional Sales Reports
A company files sales by store, then by city, then by region, then for the whole country, each report adding up the ones below it. To answer "sales in these twelve neighbouring stores" you pick a couple of city reports that sit fully inside the range plus a few stores at the edges. When one store corrects its number, only its city, its region and the country report need a new total.
🪄 The Mathematical Harmony / Magic Trick
def query(self, ql, qr, node, left, right): if ql <= left and right <= qr: return self.tree[node] # fully inside: stored sum if right < ql or left > qr: return 0 # fully outside: neutral value mid = (left + right) // 2 # partial: ask both halves return self.query(ql, qr, 2 * node + 1, left, mid) + self.query(ql, qr, 2 * node + 2, mid + 1, right) update walks down to the leaf for index, overwrites it with val, and on the way back up sets self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] for every ancestor. That recompute is what keeps every stored sum true.
💡 Summary
Node i covers [left, right], its children 2i + 1 and 2i + 2 cover the halves; 4 * n slots are always enough. Build is , and each update or query is . NumArray passes every call straight through: update sets the value (no difference needed), sumRange is query(left, right).
Not recomputing ancestors: changing only the leaf in
updateleaves every sum above it stale; on[1,3,5],update(1, 2)thensumRange(0, 2)would still return 9. Recomputeself.tree[node]after the recursive call returns.Too little space:
2 * nslots overflow whennis not a power of two; allocate4 * n.Wrong neutral value: a node fully outside the query must return
0for sums (it would be-inffor max,inffor min).Adding instead of overwriting: the segment tree stores values, so
updatesets the leaf toval; addingval(Fenwick style) double-counts the old value.
4-Phase Thought Process Model
You will see how a senior engineer picks a segment tree and explains why updates must recompute on the way up.
Pattern Recognition Signals
The 10-second spot
"Change one element" mixed with "sum of a contiguous stretch", many times and in any order: every call must be fast, not just the reads. A Segment Tree gives O(log N) for both, and the same structure would also handle range max or min if the question changed.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After every update, self.tree[node] equals the sum of nums[left..right] for the range that node covers; query uses a node's stored sum only when the node lies fully inside [ql, qr].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]after the recursiveupdate: changing only the leaf leaves every sum above it stale.self.tree = [0] * (4 * self.n):2 * noverflows whennis not a power of two.return 0for a node fully outside the query: the neutral value for sum.self.tree[node] = valat the leaf: overwrite, don't add.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Segment Tree. Each node stores the sum of a range: the root covers the whole array and each node's two children cover its two halves. For a sum query, a node fully inside the range returns its stored sum, a node fully outside returns zero, and a partly covered node asks both children; that touches about two nodes per level, so
O(log N). For an update, I walk down to the leaf for that index, overwrite it with the new value, and on the way back up recompute each ancestor as the sum of its two children. That recompute is the trap: skip it and every sum above the leaf goes stale. Building the tree isO(N), each update and query isO(log N), and it takesO(N)space with four times n slots.
So: fully inside, fully outside, or split; overwrite the leaf, then recompute every ancestor.
Complexity & Mathematical Proof
O(N) build, O(log N) query & update
Look at the recursion: _build visits each node once, and the tree has 2N - 1 nodes, so build is O(N). update follows one path from the root to a leaf (depth about log2 N) and does O(1) work per node on the way back up: O(log N). query stops at nodes fully inside or fully outside; at each level at most two nodes are partly covered, so it visits O(log N) nodes.
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.
Look at the recursion: _build visits each node once, and the tree has 2N - 1 nodes, so build is O(N). update follows one path from the root to a leaf (depth about log2 N) and does O(1) work per node on the way back up: O(log N). query stops at nodes fully inside or fully outside; at each level at most two nodes are partly covered, so it visits O(log N) nodes.
Derivation Progression
2N - 1 nodes × O(1)
_build creates every leaf and combines every internal node once.
depth × O(1) = O(log N)
One root-to-leaf path down, one recompute per ancestor on the way up.
≤ 2 partial nodes per level = O(log N)
Fully inside or fully outside nodes stop the recursion immediately.
Variable Definitions
Length of nums
A tree slot; its children are 2 * node + 1 and 2 * node + 2
Memory Architecture & Bounds
O(log N): recursion depth of update, query and _build
O(N): self.tree with 4n slots
O(1) per call
Boundary Best / Worst Cases
for a query that covers the whole array (the root answers it)
per operation; to build
per update and query
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "change one element", "sum of a contiguous stretch", "in any order". Updates and range queries interleaved: a Segment Tree (it also covers max/min/other combine operations, where a Fenwick tree does not).
and at most calls: about 16 levels, so each call visits a few dozen nodes. slots is about integers.
Forgetting the recompute leaves stale sums. Recursion depth is only about log2 N, but in a service the array often lives longer than one request: rebuild in O(N) after bulk loads instead of N separate updates.
Core Algorithmic State Invariants
After every `update`, `self.tree[node]` equals the sum of `nums[left..right]` for the range the node covers; children `2 * node + 1` and `2 * node + 2` cover the two halves.
`query` returns the stored sum for a node fully inside `[ql, qr]`, `0` for a node fully outside, and asks both children otherwise; `update` recomputes each ancestor after its child changes.
Build touches 2N - 1 nodes (O(N)); update follows one root-to-leaf path and query at most two partial nodes per level: O(log N) each, with 4n slots of space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Node i covers [left, right]; children 2i+1 and 2i+2 cover the halves | self.tree = [0] * (4 * self.n) | 4n slots always fit the tree, whatever n is. |
| Build bottom-up: leaves, then combine children | self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] | Every internal node stores the sum of its two halves. |
| Point update: go down to the leaf, overwrite it | if left == right:
self.tree[node] = val | The leaf for index holds exactly nums[index], so it is simply replaced. |
| Recompute ancestors on the way back up | self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Recompute on the way up | Without it, every sum above the changed leaf is stale. |
| Query: fully inside, fully outside, or split | if ql <= left and right <= qr: return self.tree[node]
if right < ql or left > qr: return 0 | Fully inside uses the stored sum; fully outside adds the neutral value 0; otherwise ask both halves. |
| NumArray passes calls straight through | self.seg.update(index, val)
return self.seg.query(left, right) | The tree overwrites leaves, so no difference is needed, and query takes LeetCode's 0-indexed range directly. |