Builds on Prefix Sum Map, Kernighan's Bit Trick and Prefix Sums, which you haven’t finished yet.
Fenwick Tree (Binary Indexed Tree)
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.Fenwick Tree
array ➔ isolate lowbit = x & (-x) ➔ O(log N) prefix query & update| 1 | class FenwickTree: |
| 2 | """Binary Indexed Tree (Fenwick Tree) for 1-indexed range sums. |
| 3 | Time: O(log N) update & query | Space: O(N) |
| 4 | """ |
| 5 | def __init__(self, n: int): |
| 6 | self.n = n |
| 7 | self.tree = [0] * (n + 1) |
| 8 | |
| 9 | def update(self, i: int, delta: int) -> None: |
| 10 | """Add delta to index i (1-indexed).""" |
| 11 | # 1. Walk Up, Fixing Every Block That Covers i: |
| 12 | # Adding the lowest set bit jumps from i to the next larger block that still contains it, |
| 13 | # so this visits exactly the blocks whose stored sum needs delta added. |
| 14 | while i <= self.n: |
| 15 | self.tree[i] += delta |
| 16 | i += i & (-i) # Step up to parent covering range |
| 17 | |
| 18 | def query(self, i: int) -> int: |
| 19 | """Sum elements from 1 to i (1-indexed).""" |
| 20 | total = 0 |
| 21 | |
| 22 | # 1. Walk Down, Adding Disjoint Blocks: |
| 23 | # Removing the lowest set bit jumps to just before the block tree[i] covers, so each block |
| 24 | # added is disjoint from the ones before it, and together they cover exactly 1..i once. |
| 25 | while i > 0: |
| 26 | total += self.tree[i] |
| 27 | i -= i & (-i) # Step down to next disjoint prefix |
| 28 | return total |
| 29 | |
| 30 | def range_query(self, left: int, right: int) -> int: |
| 31 | """Sum in range [left, right] inclusive.""" |
| 32 | return self.query(right) - self.query(left - 1) |
| 33 | |
| 34 | |
| 35 | class NumArray: |
| 36 | """Range Sum Query - Mutable: keep the values, send each change to the Fenwick tree.""" |
| 37 | def __init__(self, nums: list[int]): |
| 38 | self.nums = list(nums) |
| 39 | self.fenwick = FenwickTree(len(nums)) |
| 40 | |
| 41 | # 1. Seed The Tree With Every Starting Value: |
| 42 | # Each 0-based position lives one slot higher in the 1-indexed tree, so index + 1 is its i. |
| 43 | for index, val in enumerate(nums): |
| 44 | self.fenwick.update(index + 1, val) # Position index lives at i = index + 1 |
| 45 | |
| 46 | def update(self, index: int, val: int) -> None: |
| 47 | self.fenwick.update(index + 1, val - self.nums[index]) # Add the change, not the new value |
| 48 | self.nums[index] = val |
| 49 | |
| 50 | def sumRange(self, left: int, right: int) -> int: |
| 51 | return self.fenwick.range_query(left + 1, right + 1) |
self.tree[i] always equals the sum of the values at positions i - (i & -i) + 1 through i.Let tree[i] hold the sum of the block of i & (-i) values that ends at position i: query adds whole blocks while i -= i & (-i) walks down, and update fixes every block that contains i while i += i & (-i) walks up. Removing the lowest set bit jumps to just before the block tree[i] covers, so the blocks query visits never overlap and together cover exactly 1..i; adding it lands on the next larger block that also contains i. The trap is index 0: the tree is 1-indexed, and i & (-i) is 0 when i is 0, so update(0, ...) never moves and loops forever; shift every position up by one.
See it run
A Fenwick tree: query, update, query again
i -total -delta -
The column label is the position i. The first row holds the values, and the second row holds tree[i].
tree[i]the tree entry read or written at this stepblockthe values that tree[i] sumschangedthe value that update changes
The tree is built by one update per value. Each tree[i] holds the sum of the block of i & -i values that ends at position i.
Gotcha 1 of 5
- The trap
Gotcha 1: Calling
update(index, val)with a 0-basedindexMistakeself.fenwick.update(index, val)Fixself.fenwick.update(index + 1, val)What happens: The tree is 1-indexed. For
i = 0,i & (-i)is 0, soi += i & (-i)leavesiat 0. The loopwhile i <= self.nthen never ends. Shift every position up by one, sonums[index]lives ati = index + 1.Example: nums = [1, 3, 5], then sumRange(0, 2)Mistake: the loop never endsFix: returns 9
- Queries ask for the maximum over a range of values that keep being overwritten, as in Longest Increasing Subsequence II (LC 2407): a maximum can't be split into a difference of two prefixes. See Max Segment Tree
- All the updates come first and every value is read once at the end, as in Corporate Flight Bookings (LC 1109): updates and queries never mix. See Difference Array
Deep Dive
What tree[i] stores
tree[i] is the sum of a block of values that ends at position i. The block has i & -i values. The expression i & -i keeps only the lowest set bit of i, so it is the largest power of 2 that divides i.
Take nums = [3, 2, -1, 6, 5, 4, -3, 3]. The positions are 1 to 8. Position 6 is binary 110, its lowest set bit is 2, so tree[6] sums positions 5 and 6: 5 + 4 = 9. Position 4 is binary 100, so tree[4] sums positions 1 to 4: 3 + 2 - 1 + 6 = 10. Position 7 is odd, so tree[7] is just -3.
The full tree is [3, 5, -1, 10, 5, 9, -3, 19]. This matches the card's invariant: tree[i] is the sum of positions i - (i & -i) + 1 through i.
query walks down and update walks up
query(7) starts at i = 7. It adds tree[7], then removes the lowest set bit: 7 becomes 6, then 4, then 0. The blocks are position 7, positions 5 to 6, and positions 1 to 4. They do not overlap, and they cover positions 1 to 7 once. The total is -3 + 9 + 10 = 16.
Each step removes one set bit, so the loop runs at most as many times as i has set bits. That is at most floor(log2 n) + 1 steps.
update goes the other way. Changing position 3 must change every tree[k] whose block contains position 3. Those are tree[3], tree[4] and tree[8]. Adding the lowest set bit moves from 3 to 4 to 8, and the next step gives 16, which is larger than n, so the loop stops.
Example: nums[2] changes from -1 to 4. The change is 5. The three entries become 4, 15 and 24. Then query(7) visits the same blocks as before and returns -3 + 9 + 15 = 21. Only tree[4] changed among them, and it changed by exactly 5.
Add the change, and shift the index by one
FenwickTree.update adds a change to a block. It cannot set a value. So NumArray.update adds val - self.nums[index], the difference between the new and the old value. The blueprint keeps self.nums for this subtraction.
The tree is 1-indexed because the block of i is defined with i & -i. For i = 0, the expression 0 & -0 is 0, so i += i & -i leaves i at 0. The loop while i <= self.n then never ends. So nums[index] lives at i = index + 1.
sumRange(left, right) calls range_query(left + 1, right + 1). This returns query(right + 1) - query(left). The subtraction removes the prefix before left. For nums = [1, 3, 5] in Range Sum Query - Mutable (LC 307), sumRange(0, 2) is 9. After update(1, 2), it is 8.
Cost, building, and ranks
update and query each take O(log N) time. The tree takes O(N) space. Building it with N calls to update takes O(N log N) time. A single pass is faster: for each i, add tree[i] into tree[i + (i & -i)] when that position is at most n. This gives the same tree in O(N) time.
A Fenwick tree needs a way to remove the prefix before left, so it works for sums, counts and XOR, where subtraction undoes addition. It does not work as written for the minimum or the maximum, because there is no subtraction for them. A Segment Tree handles those.
To count values, use the tree as a table of counts. In Count of Smaller Numbers After Self (LC 315), replace each value by its rank from 1 to m among the sorted distinct values. Scan nums from the right. For each value with rank r, query(r - 1) is the number of smaller values already seen, and update(r, 1) records this value. For [5, 2, 6, 1] the answers are [2, 1, 1, 0].
The ranks matter because values can be negative or 0. A position of 0 or below would make update loop forever, as in the previous section.
60-Second Pitch
"A prefix-sum array answers a range sum in O(1) time, but one update rewrites up to N entries. A plain scan makes every query O(N). With many updates and many queries, I use a Fenwick tree. tree[i] holds the sum of the i & -i values that end at position i. query adds a block and removes the lowest set bit, so the blocks do not overlap and cover the prefix once. update adds the lowest set bit to reach every block that contains the position. Each loop runs at most about log N times. So update and sumRange are O(log N), and the space is O(N). I keep the 1-based index, and I add the change val - nums[index], not the new value. If the question asks for counts of earlier smaller values, I rank the values first and use the same tree as a table of counts."
Common Questions
- Why use a Fenwick tree and not a prefix-sum array?
A prefix-sum array answers
sumRangeinO(1)time, but one update changes up to N prefix sums, which costsO(N)time. A Fenwick tree makes both operationsO(log N). Use the prefix array when the values never change.- Why does the tree start at index 1?
The block of
ihasi & -ivalues. Fori = 0, that expression is 0, so the block is empty and the loopsi += i & -iandi -= i & -inever move. Starting at 1 keeps every block non-empty.- When would you use a Segment Tree instead?
When the query cannot be answered by subtracting two prefixes, for example the minimum or the maximum of a range. A Fenwick tree is shorter to write and uses less memory for sums, counts and XOR. A Segment Tree also supports range updates with lazy values.
- How do you build the tree in
O(N)time? Copy each value into
tree[i]. Then for eachifrom 1 ton, addtree[i]intotree[i + (i & -i)]when that position is at mostn. Each entry is added into its parent once, so the build makes N additions.- How does a Fenwick tree solve Count of Smaller Numbers After Self (LC 315)?
Replace each value by its rank from 1 to m. Scan from the right. For the value with rank
r, the answer isquery(r - 1), and thenupdate(r, 1)marks it as seen. Each step is O(log m), so the total isO(N log N).
SWE Reasoning
Spot it
- The array changes by single-value updates, and queries for prefix or range sums arrive between the updates.
- A prefix-sum array answers each query in
O(1)time, but one update costsO(N)time. A plain scan costsO(N)per query. Many updates and many queries together are too slow. - The question counts earlier values that are smaller (or larger) than the current one, which is a prefix count over value ranks.
- The operation can be undone by subtraction: sum, count or XOR. If it is a minimum or a maximum, use a Segment Tree instead.
The invariant, step by step
tree[i]stores the sum of the block ofi & -ivalues that ends at positioni.query(i)addstree[i], then setsi -= i & -i. The next block ends just before the current block starts.- So the blocks that
queryadds do not overlap, and together they cover positions 1 toionce. The loop ends ati = 0. - A change at position
pmust reach every block that containsp.updatestarts atpand setsi += i & -i. Each step moves to the next larger block that still containsp. - The loop stops when
iis larger thann. Everytree[i]whose block containsphas received the change, and no other entry has. - So the invariant holds after every
update, and everyqueryreturns the exact prefix sum.
Traps
- 0-based index.
update(index, val)withindex = 0leavesiat 0 and never ends. Passindex + 1. - Shifting only
right.range_query(left, right + 1)subtracts the prefix up toleft - 1, so the result also includesnums[left - 1]. Fornums = [1, 3, 5],sumRange(1, 2)returns 9 and not 8. - Adding the new value.
updateadds a change. Passingvalinstead ofval - self.nums[index]adds the whole new value on top of the old one.[1, 3, 5]withupdate(1, 2)gives 11 and not 8. - Raw values as positions. Negative values or 0 break the 1-indexed walk. Replace each value by its rank first.
- N updates to build. N calls to
updatecostO(N log N). Use the one-pass build whenO(N)is needed.
Practice
Builds on Prefix Sum Map, Kernighan's Bit Trick and Prefix Sums, which you haven’t finished yet.
Fenwick Tree (Binary Indexed Tree)
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.Fenwick Tree
array ➔ isolate lowbit = x & (-x) ➔ O(log N) prefix query & update| 1 | class FenwickTree: |
| 2 | """Binary Indexed Tree (Fenwick Tree) for 1-indexed range sums. |
| 3 | Time: O(log N) update & query | Space: O(N) |
| 4 | """ |
| 5 | def __init__(self, n: int): |
| 6 | self.n = n |
| 7 | self.tree = [0] * (n + 1) |
| 8 | |
| 9 | def update(self, i: int, delta: int) -> None: |
| 10 | """Add delta to index i (1-indexed).""" |
| 11 | # 1. Walk Up, Fixing Every Block That Covers i: |
| 12 | # Adding the lowest set bit jumps from i to the next larger block that still contains it, |
| 13 | # so this visits exactly the blocks whose stored sum needs delta added. |
| 14 | while i <= self.n: |
| 15 | self.tree[i] += delta |
| 16 | i += i & (-i) # Step up to parent covering range |
| 17 | |
| 18 | def query(self, i: int) -> int: |
| 19 | """Sum elements from 1 to i (1-indexed).""" |
| 20 | total = 0 |
| 21 | |
| 22 | # 1. Walk Down, Adding Disjoint Blocks: |
| 23 | # Removing the lowest set bit jumps to just before the block tree[i] covers, so each block |
| 24 | # added is disjoint from the ones before it, and together they cover exactly 1..i once. |
| 25 | while i > 0: |
| 26 | total += self.tree[i] |
| 27 | i -= i & (-i) # Step down to next disjoint prefix |
| 28 | return total |
| 29 | |
| 30 | def range_query(self, left: int, right: int) -> int: |
| 31 | """Sum in range [left, right] inclusive.""" |
| 32 | return self.query(right) - self.query(left - 1) |
| 33 | |
| 34 | |
| 35 | class NumArray: |
| 36 | """Range Sum Query - Mutable: keep the values, send each change to the Fenwick tree.""" |
| 37 | def __init__(self, nums: list[int]): |
| 38 | self.nums = list(nums) |
| 39 | self.fenwick = FenwickTree(len(nums)) |
| 40 | |
| 41 | # 1. Seed The Tree With Every Starting Value: |
| 42 | # Each 0-based position lives one slot higher in the 1-indexed tree, so index + 1 is its i. |
| 43 | for index, val in enumerate(nums): |
| 44 | self.fenwick.update(index + 1, val) # Position index lives at i = index + 1 |
| 45 | |
| 46 | def update(self, index: int, val: int) -> None: |
| 47 | self.fenwick.update(index + 1, val - self.nums[index]) # Add the change, not the new value |
| 48 | self.nums[index] = val |
| 49 | |
| 50 | def sumRange(self, left: int, right: int) -> int: |
| 51 | return self.fenwick.range_query(left + 1, right + 1) |
self.tree[i] always equals the sum of the values at positions i - (i & -i) + 1 through i.Let tree[i] hold the sum of the block of i & (-i) values that ends at position i: query adds whole blocks while i -= i & (-i) walks down, and update fixes every block that contains i while i += i & (-i) walks up. Removing the lowest set bit jumps to just before the block tree[i] covers, so the blocks query visits never overlap and together cover exactly 1..i; adding it lands on the next larger block that also contains i. The trap is index 0: the tree is 1-indexed, and i & (-i) is 0 when i is 0, so update(0, ...) never moves and loops forever; shift every position up by one.
See it run
A Fenwick tree: query, update, query again
i -total -delta -
The column label is the position i. The first row holds the values, and the second row holds tree[i].
tree[i]the tree entry read or written at this stepblockthe values that tree[i] sumschangedthe value that update changes
The tree is built by one update per value. Each tree[i] holds the sum of the block of i & -i values that ends at position i.
Gotcha 1 of 5
- The trap
Gotcha 1: Calling
update(index, val)with a 0-basedindexMistakeself.fenwick.update(index, val)Fixself.fenwick.update(index + 1, val)What happens: The tree is 1-indexed. For
i = 0,i & (-i)is 0, soi += i & (-i)leavesiat 0. The loopwhile i <= self.nthen never ends. Shift every position up by one, sonums[index]lives ati = index + 1.Example: nums = [1, 3, 5], then sumRange(0, 2)Mistake: the loop never endsFix: returns 9
- Queries ask for the maximum over a range of values that keep being overwritten, as in Longest Increasing Subsequence II (LC 2407): a maximum can't be split into a difference of two prefixes. See Max Segment Tree
- All the updates come first and every value is read once at the end, as in Corporate Flight Bookings (LC 1109): updates and queries never mix. See Difference Array
Deep Dive
What tree[i] stores
tree[i] is the sum of a block of values that ends at position i. The block has i & -i values. The expression i & -i keeps only the lowest set bit of i, so it is the largest power of 2 that divides i.
Take nums = [3, 2, -1, 6, 5, 4, -3, 3]. The positions are 1 to 8. Position 6 is binary 110, its lowest set bit is 2, so tree[6] sums positions 5 and 6: 5 + 4 = 9. Position 4 is binary 100, so tree[4] sums positions 1 to 4: 3 + 2 - 1 + 6 = 10. Position 7 is odd, so tree[7] is just -3.
The full tree is [3, 5, -1, 10, 5, 9, -3, 19]. This matches the card's invariant: tree[i] is the sum of positions i - (i & -i) + 1 through i.
query walks down and update walks up
query(7) starts at i = 7. It adds tree[7], then removes the lowest set bit: 7 becomes 6, then 4, then 0. The blocks are position 7, positions 5 to 6, and positions 1 to 4. They do not overlap, and they cover positions 1 to 7 once. The total is -3 + 9 + 10 = 16.
Each step removes one set bit, so the loop runs at most as many times as i has set bits. That is at most floor(log2 n) + 1 steps.
update goes the other way. Changing position 3 must change every tree[k] whose block contains position 3. Those are tree[3], tree[4] and tree[8]. Adding the lowest set bit moves from 3 to 4 to 8, and the next step gives 16, which is larger than n, so the loop stops.
Example: nums[2] changes from -1 to 4. The change is 5. The three entries become 4, 15 and 24. Then query(7) visits the same blocks as before and returns -3 + 9 + 15 = 21. Only tree[4] changed among them, and it changed by exactly 5.
Add the change, and shift the index by one
FenwickTree.update adds a change to a block. It cannot set a value. So NumArray.update adds val - self.nums[index], the difference between the new and the old value. The blueprint keeps self.nums for this subtraction.
The tree is 1-indexed because the block of i is defined with i & -i. For i = 0, the expression 0 & -0 is 0, so i += i & -i leaves i at 0. The loop while i <= self.n then never ends. So nums[index] lives at i = index + 1.
sumRange(left, right) calls range_query(left + 1, right + 1). This returns query(right + 1) - query(left). The subtraction removes the prefix before left. For nums = [1, 3, 5] in Range Sum Query - Mutable (LC 307), sumRange(0, 2) is 9. After update(1, 2), it is 8.
Cost, building, and ranks
update and query each take O(log N) time. The tree takes O(N) space. Building it with N calls to update takes O(N log N) time. A single pass is faster: for each i, add tree[i] into tree[i + (i & -i)] when that position is at most n. This gives the same tree in O(N) time.
A Fenwick tree needs a way to remove the prefix before left, so it works for sums, counts and XOR, where subtraction undoes addition. It does not work as written for the minimum or the maximum, because there is no subtraction for them. A Segment Tree handles those.
To count values, use the tree as a table of counts. In Count of Smaller Numbers After Self (LC 315), replace each value by its rank from 1 to m among the sorted distinct values. Scan nums from the right. For each value with rank r, query(r - 1) is the number of smaller values already seen, and update(r, 1) records this value. For [5, 2, 6, 1] the answers are [2, 1, 1, 0].
The ranks matter because values can be negative or 0. A position of 0 or below would make update loop forever, as in the previous section.
60-Second Pitch
"A prefix-sum array answers a range sum in O(1) time, but one update rewrites up to N entries. A plain scan makes every query O(N). With many updates and many queries, I use a Fenwick tree. tree[i] holds the sum of the i & -i values that end at position i. query adds a block and removes the lowest set bit, so the blocks do not overlap and cover the prefix once. update adds the lowest set bit to reach every block that contains the position. Each loop runs at most about log N times. So update and sumRange are O(log N), and the space is O(N). I keep the 1-based index, and I add the change val - nums[index], not the new value. If the question asks for counts of earlier smaller values, I rank the values first and use the same tree as a table of counts."
Common Questions
- Why use a Fenwick tree and not a prefix-sum array?
A prefix-sum array answers
sumRangeinO(1)time, but one update changes up to N prefix sums, which costsO(N)time. A Fenwick tree makes both operationsO(log N). Use the prefix array when the values never change.- Why does the tree start at index 1?
The block of
ihasi & -ivalues. Fori = 0, that expression is 0, so the block is empty and the loopsi += i & -iandi -= i & -inever move. Starting at 1 keeps every block non-empty.- When would you use a Segment Tree instead?
When the query cannot be answered by subtracting two prefixes, for example the minimum or the maximum of a range. A Fenwick tree is shorter to write and uses less memory for sums, counts and XOR. A Segment Tree also supports range updates with lazy values.
- How do you build the tree in
O(N)time? Copy each value into
tree[i]. Then for eachifrom 1 ton, addtree[i]intotree[i + (i & -i)]when that position is at mostn. Each entry is added into its parent once, so the build makes N additions.- How does a Fenwick tree solve Count of Smaller Numbers After Self (LC 315)?
Replace each value by its rank from 1 to m. Scan from the right. For the value with rank
r, the answer isquery(r - 1), and thenupdate(r, 1)marks it as seen. Each step is O(log m), so the total isO(N log N).
SWE Reasoning
Spot it
- The array changes by single-value updates, and queries for prefix or range sums arrive between the updates.
- A prefix-sum array answers each query in
O(1)time, but one update costsO(N)time. A plain scan costsO(N)per query. Many updates and many queries together are too slow. - The question counts earlier values that are smaller (or larger) than the current one, which is a prefix count over value ranks.
- The operation can be undone by subtraction: sum, count or XOR. If it is a minimum or a maximum, use a Segment Tree instead.
The invariant, step by step
tree[i]stores the sum of the block ofi & -ivalues that ends at positioni.query(i)addstree[i], then setsi -= i & -i. The next block ends just before the current block starts.- So the blocks that
queryadds do not overlap, and together they cover positions 1 toionce. The loop ends ati = 0. - A change at position
pmust reach every block that containsp.updatestarts atpand setsi += i & -i. Each step moves to the next larger block that still containsp. - The loop stops when
iis larger thann. Everytree[i]whose block containsphas received the change, and no other entry has. - So the invariant holds after every
update, and everyqueryreturns the exact prefix sum.
Traps
- 0-based index.
update(index, val)withindex = 0leavesiat 0 and never ends. Passindex + 1. - Shifting only
right.range_query(left, right + 1)subtracts the prefix up toleft - 1, so the result also includesnums[left - 1]. Fornums = [1, 3, 5],sumRange(1, 2)returns 9 and not 8. - Adding the new value.
updateadds a change. Passingvalinstead ofval - self.nums[index]adds the whole new value on top of the old one.[1, 3, 5]withupdate(1, 2)gives 11 and not 8. - Raw values as positions. Negative values or 0 break the 1-indexed walk. Replace each value by its rank first.
- N updates to build. N calls to
updatecostO(N log N). Use the one-pass build whenO(N)is needed.