Builds on Bottom-Up DFS, Prefix Sum Map and Prefix Sums, which you haven’t finished yet.
Segment Tree (Range Sums With Point Updates)
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).
[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.Segment Tree
array ➔ binary tree of range sums ➔ O(log N) point update & range sum| 1 | class SegmentTree: |
| 2 | """Sum Segment Tree with Point Updates. |
| 3 | Node i covers [left, right]; its children are 2i+1 (left half) and 2i+2 (right half). |
| 4 | Time: O(N) build, O(log N) query & update | Space: O(N) |
| 5 | """ |
| 6 | def __init__(self, nums: list[int]) -> None: |
| 7 | self.n = len(nums) |
| 8 | self.tree = [0] * (4 * self.n) # tree[node] is the sum of the slots node covers; 4n is always enough room |
| 9 | self._build(nums, 0, 0, self.n - 1) |
| 10 | |
| 11 | def _build(self, nums: list[int], node: int, left: int, right: int) -> None: |
| 12 | # 1. Fill A Leaf With Its One Element, Else Build Both Halves First: |
| 13 | # A node's sum is the sum of its two halves, so both children must be built before this node can combine them. |
| 14 | if left == right: |
| 15 | self.tree[node] = nums[left] # Leaf: one array element |
| 16 | return |
| 17 | mid = (left + right) // 2 |
| 18 | self._build(nums, 2 * node + 1, left, mid) |
| 19 | self._build(nums, 2 * node + 2, mid + 1, right) |
| 20 | self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Combine the two halves |
| 21 | |
| 22 | def update(self, index: int, val: int, node: int = 0, left: int = 0, right: int = -1) -> None: |
| 23 | # 1. Default The Range, Then Stop At The Leaf For index: |
| 24 | # The first call omits left/right, so they default here; once left == right only one |
| 25 | # slot is left in the range, and that slot is index, so the leaf's own value is set. |
| 26 | if right == -1: |
| 27 | right = self.n - 1 # Default: start at the whole range |
| 28 | if left == right: |
| 29 | self.tree[node] = val # Reached the leaf for index |
| 30 | return |
| 31 | |
| 32 | # 2. Recurse Into The Half That Contains index, Then Recompute On The Way Up: |
| 33 | # index lies in exactly one half, so only one child is visited; recomputing this node's |
| 34 | # sum from both children afterward keeps every ancestor's stored sum in sync with the new leaf. |
| 35 | mid = (left + right) // 2 |
| 36 | if index <= mid: |
| 37 | self.update(index, val, 2 * node + 1, left, mid) # Go left |
| 38 | else: |
| 39 | self.update(index, val, 2 * node + 2, mid + 1, right) # Go right |
| 40 | self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Recompute on the way up |
| 41 | |
| 42 | def query(self, ql: int, qr: int, node: int = 0, left: int = 0, right: int = -1) -> int: |
| 43 | # 1. Default The Range, Then Resolve Full Overlap Or No Overlap: |
| 44 | # A node fully inside [ql, qr] can answer from its own stored sum; a node fully outside |
| 45 | # contributes 0, since it holds none of the requested slots. |
| 46 | if right == -1: |
| 47 | right = self.n - 1 |
| 48 | if ql <= left and right <= qr: |
| 49 | return self.tree[node] # Fully inside the query: use the stored sum |
| 50 | if right < ql or left > qr: |
| 51 | return 0 # Fully outside: contributes nothing |
| 52 | |
| 53 | # 2. Split On Partial Overlap And Add Both Halves: |
| 54 | # Neither child's range is fully inside or outside, so both are queried and their sums are added. |
| 55 | mid = (left + right) // 2 # Partial overlap: split into both halves |
| 56 | return (self.query(ql, qr, 2 * node + 1, left, mid) + |
| 57 | self.query(ql, qr, 2 * node + 2, mid + 1, right)) |
| 58 | |
| 59 | |
| 60 | class NumArray: |
| 61 | """Range Sum Query - Mutable: every call goes straight to the segment tree.""" |
| 62 | def __init__(self, nums: list[int]): |
| 63 | self.seg = SegmentTree(nums) |
| 64 | |
| 65 | def update(self, index: int, val: int) -> None: |
| 66 | self.seg.update(index, val) # The leaf is overwritten with val, then its ancestors recomputed |
| 67 | |
| 68 | def sumRange(self, left: int, right: int) -> int: |
| 69 | return self.seg.query(left, right) |
update, self.tree[node] equals the sum of the slots left..right that node covers.Node node stores the sum of the slots left..right it covers, and its children 2 * node + 1 and 2 * node + 2 store the sums of the two halves. So update sets one leaf and, on the way back up, rebuilds each ancestor's sum from its two children. query(ql, qr) splits the range the same way: a node fully inside [ql, qr] returns its stored self.tree[node], a node fully outside returns 0, and a node that overlaps only part of the range adds the answers of both children. At most two nodes per level overlap only part of the range, so every update and query stays on a few nodes per level. The trap is the last line of update, self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]. If it is missing, the leaf changes but every ancestor keeps its old sum, and a later query that returns a stored self.tree[node] reads that old sum.
See it run
A sum segment tree: query, update, query again
node -total -
Each circle shows the stored sum of the node. The node numbers are indices in self.tree, and the node at the top is node 0. The nums row shows the array.
splita node that overlaps only part of the range, or lies on the update pathinsidea node inside the query that returns its stored sumoutsidea node outside the query that returns 0changeda node whose stored sum was just writtenstalean ancestor that still holds its old sum
The tree is built. Each node holds the sum of the slots it covers, and each leaf holds one array value.
Gotcha 1 of 5
- The trap
Gotcha 1: Changing the leaf but not recomputing its ancestors
Mistakeelse: self.update(index, val, 2 * node + 2, mid + 1, right)Fixelse: self.update(index, val, 2 * node + 2, mid + 1, right) self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]What happens:
updatechanges the leaf forindex, then returns up the recursion. Each node on the way holds the sum of its range. Without the lineself.tree[node] = ..., those nodes keep their old sum. A laterquerythat fully covers such a node returns its storedself.tree[node]and misses the new value. Fornums = [1, 3, 5], the root keeps9afterupdate(1, 2), although the sum is now8.Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)Mistake: returns 9Fix: returns 8
- The only operations are adding to one position and summing a prefix, as in Create Sorted Array through Instructions (LC 1649): a Fenwick tree does that in much less code, and you need a segment tree only when a node must store something a difference of two prefixes cannot give. See Fenwick Tree
- The array never changes after it is built, as in Range Sum Query - Immutable (LC 303): one prefix-sum array answers every range sum in
O(1), with no tree. See Prefix Sums
Deep Dive
What self.tree[node] stores
A node covers a stretch of slots left..right and stores their sum. The root covers every slot. A node that covers more than one slot has two children: the left child covers left..mid, and the right child covers mid + 1..right. A node that covers one slot is a leaf and stores that array value.
Take nums = [2, 5, 1, 4, 3, 6]. The root, node 0, covers slots 0 to 5 and stores 21. Node 1 covers slots 0 to 2 and stores 8. Node 2 covers slots 3 to 5 and stores 13. Each node stores the sum of its two children, so 8 + 13 = 21.
The children of node sit at 2 * node + 1 and 2 * node + 2 in the list self.tree. This is the card's invariant: after every update, self.tree[node] equals the sum of the slots that node covers.
query takes a stored sum only from a node inside the range
query(ql, qr) visits a node and compares its slots with [ql, qr]. There are three cases. If the node lies inside the range, it returns self.tree[node] and does not look at its children. If it lies outside, it returns 0. If it overlaps only part of the range, it asks both children and adds their answers.
Example: sumRange(1, 4) on [2, 5, 1, 4, 3, 6]. Nodes 0, 1 and 3 overlap partly, so they split. Node 7 covers only slot 0, so it returns 0. Node 8 covers only slot 1, so it returns 5. Node 4 covers only slot 2, so it returns 1. Node 2 splits again, and node 5 covers slots 3 and 4, so it returns 7. Node 6 covers slot 5 and returns 0. The total is 5 + 1 + 7 = 13, which matches 5 + 1 + 4 + 3.
The order of the two tests matters. A node fully inside is checked first. A node that only overlaps must never return its stored sum, because that sum also counts slots outside [ql, qr].
update sets one leaf and rebuilds the sums above it
update(index, val) goes to the one child whose range contains index. At the leaf it sets self.tree[node] = val. Then, as each call returns, it recomputes self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2].
In the example, update(2, 7) visits nodes 0, 1 and 4. Node 4 changes from 1 to 7. Node 1 becomes 7 + 7 = 14, and node 0 becomes 14 + 13 = 27. Then sumRange(1, 4) returns 5 + 7 + 7 = 19.
The recompute lines are the whole point of update. Between the leaf write and the recompute, node 1 and node 0 still hold 8 and 21. A query that fully covers node 1 would read the old 8.
Cost, space, and what a Fenwick Tree cannot do
The tree has 2 * n - 1 nodes, and its height is about log2 n. update visits one node per level, so it takes O(log N) time. At most 2 nodes per level overlap the query only in part, and each of them asks 2 children. So query visits at most 4 nodes per level, which is O(log N) time. The build visits every node once, so it takes O(N) time.
The list self.tree has 4 * n slots. Because a half can be one slot larger than the other, the last index can pass 2 * n. For n = 6, node 12 exists, and a list of 2 * n = 12 slots has no index 12. 4 * n slots are always enough.
The Fenwick Tree card answers the same sum queries with less code. It needs a subtraction to remove the prefix before left. A Segment Tree needs no subtraction, because it adds stored sums of ranges that are already exact. So it can also store the minimum or the maximum of each range, where subtraction does not exist.
60-Second Pitch
"A prefix-sum array answers a range sum quickly, but one update rewrites up to N entries. A plain loop makes each query O(N). With many updates and many queries, I use a Segment Tree. Each node node stores the sum of the slots left..right it covers, and its children store the two halves. update goes down to one leaf, sets it, and recomputes each ancestor from its two children on the way back up. query returns the stored sum when a node lies inside the range, returns 0 when it lies outside, and splits into both children otherwise. At most 2 nodes per level split, so both operations are O(log N). The build is O(N), and the space is O(N) with 4 * n slots. If the question asks for a minimum or a maximum, I use the same tree and change the combine step. A Fenwick Tree cannot do that."
Common Questions
- Why is
updateO(log N)when it changes one value but many nodes hold a sum? Only the nodes whose range contains
indexcan hold a wrong sum. There is one such node per level, because the ranges at one level do not overlap. The tree has aboutlog2 nlevels, soupdatetouches aboutlog2 nnodes.- Why does
queryvisit only a few nodes per level? A node that splits overlaps the range only in part. Such a node contains an end of the range, either
qlorqr. A level has at most one node that containsqland one that containsqr, so at most 2 nodes split per level. Each asks 2 children, so a level has at most 4 visited nodes.- How would you change the tree to answer the maximum of a range?
Store the maximum of each range instead of the sum. Combine two children with
max, and return negative infinity from a node outside the range. The three cases ofqueryand the recompute line ofupdatestay the same. A Fenwick Tree cannot do this, because it needs subtraction.- What would you do if the problem asked to add a value to every slot in a range?
Use lazy propagation. A node keeps a pending change for its whole range. A query or update that goes below that node first passes the pending change to the two children. Both operations stay
O(log N).- When do you choose a Fenwick Tree instead?
When the operation can be undone by subtraction, as with sums, counts and XOR. The Fenwick Tree card is shorter to write and uses N slots, not 4N. The Segment Tree is the choice when you need the minimum or the maximum, or a range update.
SWE Reasoning
Spot it
- The array changes one value at a time, and range questions arrive between the changes. Range Sum Query - Mutable (LC 307) is the model problem.
- A prefix-sum array makes each query
O(1)but each updateO(N). A plain loop makes each queryO(N). Many updates and many queries together are too slow for both. - The question asks for a combined value of a range, such as a sum, a minimum or a maximum, and the combine step is associative: grouping the parts differently gives the same answer.
- The operation has no inverse, such as the minimum or the maximum. A Fenwick Tree cannot subtract a prefix here, so a Segment Tree is the choice.
The invariant, step by step
_buildmakes a leaf for each slot, and it sets each inner node to the sum of its two children. So the invariant holds for every node after the build.update(index, val)goes down only through nodes whose range containsindex. At the leaf it setsself.tree[node] = val.- Only the nodes on that path cover
index, so only they can hold a wrong sum. Every other node covers slots that did not change. - On the way back up, each node on the path sets
self.tree[node]to the sum of its two children. The lower child is already correct, so the parent becomes correct. The invariant holds again for the whole path. query(ql, qr)returnsself.tree[node]only whenql <= left and right <= qr. Then the stored sum is exactly the sum of slots that are inside the range.- The nodes that return a stored sum cover disjoint slots, and together they cover
ql..qronce. Their total is the exact range sum.
Traps
- Missing recompute. If the last line of
updateis absent, the leaf changes and the ancestors keep old sums. For[1, 3, 5]afterupdate(1, 2),sumRange(0, 2)returns9and not8. - Overlap test for a stored sum.
if left <= qr and ql <= rightreturns a sum that includes slots outside the range. For[1, 3, 5],sumRange(0, 1)returns9and not4. - Adding instead of setting.
self.tree[node] += valat the leaf keeps the old value. LeetCode'supdatereplaces the value. For[1, 3, 5]afterupdate(1, 2), the sum is11and not8. - Too few slots. A list of
2 * nslots raises IndexError forn = 6. Use4 * n. - Updating a range by many point updates. Each point update costs
O(log N). A change to a whole range needs lazy propagation, which keeps a pending change at a node and passes it down only when needed.
Practice
Builds on Bottom-Up DFS, Prefix Sum Map and Prefix Sums, which you haven’t finished yet.
Segment Tree (Range Sums With Point Updates)
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).
[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.Segment Tree
array ➔ binary tree of range sums ➔ O(log N) point update & range sum| 1 | class SegmentTree: |
| 2 | """Sum Segment Tree with Point Updates. |
| 3 | Node i covers [left, right]; its children are 2i+1 (left half) and 2i+2 (right half). |
| 4 | Time: O(N) build, O(log N) query & update | Space: O(N) |
| 5 | """ |
| 6 | def __init__(self, nums: list[int]) -> None: |
| 7 | self.n = len(nums) |
| 8 | self.tree = [0] * (4 * self.n) # tree[node] is the sum of the slots node covers; 4n is always enough room |
| 9 | self._build(nums, 0, 0, self.n - 1) |
| 10 | |
| 11 | def _build(self, nums: list[int], node: int, left: int, right: int) -> None: |
| 12 | # 1. Fill A Leaf With Its One Element, Else Build Both Halves First: |
| 13 | # A node's sum is the sum of its two halves, so both children must be built before this node can combine them. |
| 14 | if left == right: |
| 15 | self.tree[node] = nums[left] # Leaf: one array element |
| 16 | return |
| 17 | mid = (left + right) // 2 |
| 18 | self._build(nums, 2 * node + 1, left, mid) |
| 19 | self._build(nums, 2 * node + 2, mid + 1, right) |
| 20 | self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Combine the two halves |
| 21 | |
| 22 | def update(self, index: int, val: int, node: int = 0, left: int = 0, right: int = -1) -> None: |
| 23 | # 1. Default The Range, Then Stop At The Leaf For index: |
| 24 | # The first call omits left/right, so they default here; once left == right only one |
| 25 | # slot is left in the range, and that slot is index, so the leaf's own value is set. |
| 26 | if right == -1: |
| 27 | right = self.n - 1 # Default: start at the whole range |
| 28 | if left == right: |
| 29 | self.tree[node] = val # Reached the leaf for index |
| 30 | return |
| 31 | |
| 32 | # 2. Recurse Into The Half That Contains index, Then Recompute On The Way Up: |
| 33 | # index lies in exactly one half, so only one child is visited; recomputing this node's |
| 34 | # sum from both children afterward keeps every ancestor's stored sum in sync with the new leaf. |
| 35 | mid = (left + right) // 2 |
| 36 | if index <= mid: |
| 37 | self.update(index, val, 2 * node + 1, left, mid) # Go left |
| 38 | else: |
| 39 | self.update(index, val, 2 * node + 2, mid + 1, right) # Go right |
| 40 | self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Recompute on the way up |
| 41 | |
| 42 | def query(self, ql: int, qr: int, node: int = 0, left: int = 0, right: int = -1) -> int: |
| 43 | # 1. Default The Range, Then Resolve Full Overlap Or No Overlap: |
| 44 | # A node fully inside [ql, qr] can answer from its own stored sum; a node fully outside |
| 45 | # contributes 0, since it holds none of the requested slots. |
| 46 | if right == -1: |
| 47 | right = self.n - 1 |
| 48 | if ql <= left and right <= qr: |
| 49 | return self.tree[node] # Fully inside the query: use the stored sum |
| 50 | if right < ql or left > qr: |
| 51 | return 0 # Fully outside: contributes nothing |
| 52 | |
| 53 | # 2. Split On Partial Overlap And Add Both Halves: |
| 54 | # Neither child's range is fully inside or outside, so both are queried and their sums are added. |
| 55 | mid = (left + right) // 2 # Partial overlap: split into both halves |
| 56 | return (self.query(ql, qr, 2 * node + 1, left, mid) + |
| 57 | self.query(ql, qr, 2 * node + 2, mid + 1, right)) |
| 58 | |
| 59 | |
| 60 | class NumArray: |
| 61 | """Range Sum Query - Mutable: every call goes straight to the segment tree.""" |
| 62 | def __init__(self, nums: list[int]): |
| 63 | self.seg = SegmentTree(nums) |
| 64 | |
| 65 | def update(self, index: int, val: int) -> None: |
| 66 | self.seg.update(index, val) # The leaf is overwritten with val, then its ancestors recomputed |
| 67 | |
| 68 | def sumRange(self, left: int, right: int) -> int: |
| 69 | return self.seg.query(left, right) |
update, self.tree[node] equals the sum of the slots left..right that node covers.Node node stores the sum of the slots left..right it covers, and its children 2 * node + 1 and 2 * node + 2 store the sums of the two halves. So update sets one leaf and, on the way back up, rebuilds each ancestor's sum from its two children. query(ql, qr) splits the range the same way: a node fully inside [ql, qr] returns its stored self.tree[node], a node fully outside returns 0, and a node that overlaps only part of the range adds the answers of both children. At most two nodes per level overlap only part of the range, so every update and query stays on a few nodes per level. The trap is the last line of update, self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]. If it is missing, the leaf changes but every ancestor keeps its old sum, and a later query that returns a stored self.tree[node] reads that old sum.
See it run
A sum segment tree: query, update, query again
node -total -
Each circle shows the stored sum of the node. The node numbers are indices in self.tree, and the node at the top is node 0. The nums row shows the array.
splita node that overlaps only part of the range, or lies on the update pathinsidea node inside the query that returns its stored sumoutsidea node outside the query that returns 0changeda node whose stored sum was just writtenstalean ancestor that still holds its old sum
The tree is built. Each node holds the sum of the slots it covers, and each leaf holds one array value.
Gotcha 1 of 5
- The trap
Gotcha 1: Changing the leaf but not recomputing its ancestors
Mistakeelse: self.update(index, val, 2 * node + 2, mid + 1, right)Fixelse: self.update(index, val, 2 * node + 2, mid + 1, right) self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]What happens:
updatechanges the leaf forindex, then returns up the recursion. Each node on the way holds the sum of its range. Without the lineself.tree[node] = ..., those nodes keep their old sum. A laterquerythat fully covers such a node returns its storedself.tree[node]and misses the new value. Fornums = [1, 3, 5], the root keeps9afterupdate(1, 2), although the sum is now8.Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)Mistake: returns 9Fix: returns 8
- The only operations are adding to one position and summing a prefix, as in Create Sorted Array through Instructions (LC 1649): a Fenwick tree does that in much less code, and you need a segment tree only when a node must store something a difference of two prefixes cannot give. See Fenwick Tree
- The array never changes after it is built, as in Range Sum Query - Immutable (LC 303): one prefix-sum array answers every range sum in
O(1), with no tree. See Prefix Sums
Deep Dive
What self.tree[node] stores
A node covers a stretch of slots left..right and stores their sum. The root covers every slot. A node that covers more than one slot has two children: the left child covers left..mid, and the right child covers mid + 1..right. A node that covers one slot is a leaf and stores that array value.
Take nums = [2, 5, 1, 4, 3, 6]. The root, node 0, covers slots 0 to 5 and stores 21. Node 1 covers slots 0 to 2 and stores 8. Node 2 covers slots 3 to 5 and stores 13. Each node stores the sum of its two children, so 8 + 13 = 21.
The children of node sit at 2 * node + 1 and 2 * node + 2 in the list self.tree. This is the card's invariant: after every update, self.tree[node] equals the sum of the slots that node covers.
query takes a stored sum only from a node inside the range
query(ql, qr) visits a node and compares its slots with [ql, qr]. There are three cases. If the node lies inside the range, it returns self.tree[node] and does not look at its children. If it lies outside, it returns 0. If it overlaps only part of the range, it asks both children and adds their answers.
Example: sumRange(1, 4) on [2, 5, 1, 4, 3, 6]. Nodes 0, 1 and 3 overlap partly, so they split. Node 7 covers only slot 0, so it returns 0. Node 8 covers only slot 1, so it returns 5. Node 4 covers only slot 2, so it returns 1. Node 2 splits again, and node 5 covers slots 3 and 4, so it returns 7. Node 6 covers slot 5 and returns 0. The total is 5 + 1 + 7 = 13, which matches 5 + 1 + 4 + 3.
The order of the two tests matters. A node fully inside is checked first. A node that only overlaps must never return its stored sum, because that sum also counts slots outside [ql, qr].
update sets one leaf and rebuilds the sums above it
update(index, val) goes to the one child whose range contains index. At the leaf it sets self.tree[node] = val. Then, as each call returns, it recomputes self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2].
In the example, update(2, 7) visits nodes 0, 1 and 4. Node 4 changes from 1 to 7. Node 1 becomes 7 + 7 = 14, and node 0 becomes 14 + 13 = 27. Then sumRange(1, 4) returns 5 + 7 + 7 = 19.
The recompute lines are the whole point of update. Between the leaf write and the recompute, node 1 and node 0 still hold 8 and 21. A query that fully covers node 1 would read the old 8.
Cost, space, and what a Fenwick Tree cannot do
The tree has 2 * n - 1 nodes, and its height is about log2 n. update visits one node per level, so it takes O(log N) time. At most 2 nodes per level overlap the query only in part, and each of them asks 2 children. So query visits at most 4 nodes per level, which is O(log N) time. The build visits every node once, so it takes O(N) time.
The list self.tree has 4 * n slots. Because a half can be one slot larger than the other, the last index can pass 2 * n. For n = 6, node 12 exists, and a list of 2 * n = 12 slots has no index 12. 4 * n slots are always enough.
The Fenwick Tree card answers the same sum queries with less code. It needs a subtraction to remove the prefix before left. A Segment Tree needs no subtraction, because it adds stored sums of ranges that are already exact. So it can also store the minimum or the maximum of each range, where subtraction does not exist.
60-Second Pitch
"A prefix-sum array answers a range sum quickly, but one update rewrites up to N entries. A plain loop makes each query O(N). With many updates and many queries, I use a Segment Tree. Each node node stores the sum of the slots left..right it covers, and its children store the two halves. update goes down to one leaf, sets it, and recomputes each ancestor from its two children on the way back up. query returns the stored sum when a node lies inside the range, returns 0 when it lies outside, and splits into both children otherwise. At most 2 nodes per level split, so both operations are O(log N). The build is O(N), and the space is O(N) with 4 * n slots. If the question asks for a minimum or a maximum, I use the same tree and change the combine step. A Fenwick Tree cannot do that."
Common Questions
- Why is
updateO(log N)when it changes one value but many nodes hold a sum? Only the nodes whose range contains
indexcan hold a wrong sum. There is one such node per level, because the ranges at one level do not overlap. The tree has aboutlog2 nlevels, soupdatetouches aboutlog2 nnodes.- Why does
queryvisit only a few nodes per level? A node that splits overlaps the range only in part. Such a node contains an end of the range, either
qlorqr. A level has at most one node that containsqland one that containsqr, so at most 2 nodes split per level. Each asks 2 children, so a level has at most 4 visited nodes.- How would you change the tree to answer the maximum of a range?
Store the maximum of each range instead of the sum. Combine two children with
max, and return negative infinity from a node outside the range. The three cases ofqueryand the recompute line ofupdatestay the same. A Fenwick Tree cannot do this, because it needs subtraction.- What would you do if the problem asked to add a value to every slot in a range?
Use lazy propagation. A node keeps a pending change for its whole range. A query or update that goes below that node first passes the pending change to the two children. Both operations stay
O(log N).- When do you choose a Fenwick Tree instead?
When the operation can be undone by subtraction, as with sums, counts and XOR. The Fenwick Tree card is shorter to write and uses N slots, not 4N. The Segment Tree is the choice when you need the minimum or the maximum, or a range update.
SWE Reasoning
Spot it
- The array changes one value at a time, and range questions arrive between the changes. Range Sum Query - Mutable (LC 307) is the model problem.
- A prefix-sum array makes each query
O(1)but each updateO(N). A plain loop makes each queryO(N). Many updates and many queries together are too slow for both. - The question asks for a combined value of a range, such as a sum, a minimum or a maximum, and the combine step is associative: grouping the parts differently gives the same answer.
- The operation has no inverse, such as the minimum or the maximum. A Fenwick Tree cannot subtract a prefix here, so a Segment Tree is the choice.
The invariant, step by step
_buildmakes a leaf for each slot, and it sets each inner node to the sum of its two children. So the invariant holds for every node after the build.update(index, val)goes down only through nodes whose range containsindex. At the leaf it setsself.tree[node] = val.- Only the nodes on that path cover
index, so only they can hold a wrong sum. Every other node covers slots that did not change. - On the way back up, each node on the path sets
self.tree[node]to the sum of its two children. The lower child is already correct, so the parent becomes correct. The invariant holds again for the whole path. query(ql, qr)returnsself.tree[node]only whenql <= left and right <= qr. Then the stored sum is exactly the sum of slots that are inside the range.- The nodes that return a stored sum cover disjoint slots, and together they cover
ql..qronce. Their total is the exact range sum.
Traps
- Missing recompute. If the last line of
updateis absent, the leaf changes and the ancestors keep old sums. For[1, 3, 5]afterupdate(1, 2),sumRange(0, 2)returns9and not8. - Overlap test for a stored sum.
if left <= qr and ql <= rightreturns a sum that includes slots outside the range. For[1, 3, 5],sumRange(0, 1)returns9and not4. - Adding instead of setting.
self.tree[node] += valat the leaf keeps the old value. LeetCode'supdatereplaces the value. For[1, 3, 5]afterupdate(1, 2), the sum is11and not8. - Too few slots. A list of
2 * nslots raises IndexError forn = 6. Use4 * n. - Updating a range by many point updates. Each point update costs
O(log N). A change to a whole range needs lazy propagation, which keeps a pending change at a node and passes it down only when needed.