Lazy propagation and a note on Fenwick trees in Python

Why it matters

Point updates change one item. Some problems change a whole range at once, such as "add 10 to every item from index 1 to 3" or "set every lamp in a corridor to the same brightness." Doing that item by item costs O(n) for each change, which is too slow when the ranges are large and the changes are frequent. Lazy propagation makes a range update cost O(log n) as well, and it keeps the same tree you already know.

This lesson has three parts. You will learn the idea of a lazy note and the two helper steps that make it work. You will write a range-add tree and check it against a plain list. Finally, you will meet the Fenwick tree, a smaller structure that handles prefix sums and point updates, and learn when it is the better choice.

Words you need first

A range update changes every item in a block at once. add(l, r, v) adds v to each item from l to r. This is different from a point update, which changes one item.

A lazy value is one that waits. The word is used in computing for work that is postponed until someone needs the result. A lazy value is a note: it says the work still needs to be done, and it is written down instead of carried out at once.

A pending note is one that has not yet been passed on to the children of a node. Think of it as a message that is waiting to be delivered.

Push down means passing a pending note from a node to its two children, and then clearing the note. After a push, the children carry the change and the node has no note left.

The idea: a note instead of a rewrite

Consider the range update add(1, 3, 10) on a tree over six items. The range covers indexes 1, 2 and 3. Without laziness, you would visit every leaf in that range and add 10 to each. A range of a million items would then cost a million changes, which is far too slow.

Lazy propagation takes a shortcut. When the update reaches a node whose whole segment is inside the range, the node does not visit its children. It updates its own sum, because it knows the sum changes by 10 times the number of items. Then it leaves a note: "every item below me still needs +10." The children are not touched yet.

Here is an everyday picture. A teacher says to the front row, "everyone in this row gets 10 bonus marks." The teacher does not walk down the row and write on every student's sheet. The teacher writes one note on a card that sits on the row. When a particular student's marks are needed, the note is applied to that student first. The work is paid only when someone looks.

The note can be wrong for a child if you read the child before the note is delivered. That is the real danger, and the rule that prevents it is simple. Before you read or change a node's children, push the node's note down to them.

What each node stores

For each node we store two numbers.

The first is sum[node], the correct sum of the node's segment, including every change that has already reached this node. This number is always up to date for the node itself.

The second is lazy[node], a pending amount to add to every item in each child's segment. It has not been passed to the children yet. When it is zero, there is nothing pending.

Notice what sum[node] means. It already includes every change made at this node or above it. What it does not know is whether the children have heard about those changes. That is the reason for the lazy note.

The two helper steps

There are two small helpers, and most of the logic lives in them.

Apply. To apply a value v to a node, add v times the number of items in the node's segment to its sum, and add v to its note. The number of items in [l..r] is r - l + 1. In the example above, a node covering two items grows its sum by 2 * 10 = 20 when it receives +10.

Push down. Before going into a node's children, pass the note to both children. Apply the note to the left child and then to the right child. Then clear the note in the node. If the note is zero, skip the work.

Apply is used in two places. It is used when an update covers a whole node, and it is used when a push delivers a note to a child. The same rule in both places keeps the sums correct.

Range add and range sum

With the helpers in place, the update and the query follow the same three cases as before.

For add(l, r, v), the search has three branches. If the node does not overlap the range, return. If the node is fully inside the range, apply v to the node and stop, leaving its children with the note. If the node is partly inside the range, push its note down, recurse into both children, and recompute the node's sum from its children.

For query(l, r), the search has three branches too. If the node does not overlap, return 0. If the node is fully inside, return sum[node], which is already correct because every note above it has been applied to it. If the node is partly inside, push its note down so the children are correct, recurse into both children, and add their answers.

Here is the full program. It builds a tree over [1, 3, 5, 7, 9, 11], adds 10 to indexes 1 to 3, and asks three sums.

The output is:

66
28
37

After adding 10 to indexes 1 to 3, the list is [1, 13, 15, 17, 9, 11]. The total is 1 + 13 + 15 + 17 + 9 + 11 = 66. Indexes 1 and 2 give 13 + 15 = 28. Indexes 3 to 5 give 17 + 9 + 11 = 37.

Now watch what the update does on the tree. The update add(1, 3, 10) reaches the root, which is partly covered. The root pushes its note, which is zero, so nothing moves. It recurses into [0..2], which is partly covered, and then into [0..1], which is also partly covered. The leaf [1..1] is fully covered, so it receives 10. Its sibling [0..0] is outside the range and is left alone. Back at [0..2], the leaf [2..2] is fully covered and receives 10 too. On the right side, [3..5] is partly covered, and its child [3..4] is partly covered. The leaf [3..3] receives 10, while [4..4] and [5..5] are outside the range.

No internal node was fully inside the range, so no note was left above a leaf.

A note stays on an internal node only when the range covers that whole node. The next program does that. It adds 10 to indexes 0 to 3, which covers the whole node [0..2]. Then it prints every node with its sum and its pending note.

The output is:

node 1 [0..5] sum 76 note 0
  node 2 [0..2] sum 39 note 10
    node 4 [0..1] sum 4 note 0
      node 8 [0..0] sum 1 note 0
      node 9 [1..1] sum 3 note 0
    node 5 [2..2] sum 5 note 0
  node 3 [3..5] sum 37 note 0
    node 6 [3..4] sum 26 note 0
      node 12 [3..3] sum 17 note 10
      node 13 [4..4] sum 9 note 0
    node 7 [5..5] sum 11 note 0
76
28
37

Read the dump from the top. The root holds 76, which is already right, because every change above the leaves updates it directly. Node 2 covers [0..2]. It holds 39, the correct sum, and a note of 10. Its children, node 4 with sum 4 and node 5 with sum 5, still show the old values, because the note has not been passed down. Node 3 holds 37, which is correct, because its own children were updated in this same call. The leaf [3..3] also carries a note of 10. That note is harmless, because a leaf has no children to pass it to.

Think of node 2 at this moment. It holds the right sum, 39, but its children still show 4 and 5. The note of +10 says each item below it needs 10 more. When a later operation needs a child, the push delivers the note. The children become 24 and 15, and the note on the node is cleared.

Now ask query(1, 2) on this state. The root is partly covered, so it pushes its zero note and recurses. Node 2 covers [0..2], which is partly covered by the range [1..2], so it pushes its note of 10 to its children. Node 4 gains 20, because each of its two items gets 10, so its sum becomes 24. Node 4 now holds a note of 10 of its own. Node 5 becomes 15, and node 2's note is cleared. Next, node 4 is partly covered, so it pushes its new note. Its leaves become 11 and 13. The leaf for index 1 is inside the range and returns 13. The leaf for index 0 is outside and returns 0. Node 5 is inside the range and returns 15. The answer is 13 + 15 = 28, which matches the output.

The query query(3, 5) follows the same rules. The root is partly covered and its note is zero, so the push changes nothing. The node [3..5] is fully covered, so the search returns its stored sum, 37, at once without visiting its children. The answer is 17 + 9 + 11 = 37.

Why the query must push too

A common error is to push only during the update. The query looks harmless, because it only reads. But the query reads children, and a child can be stale if the note above it has not been delivered. So the query must push before it recurses, the same way the update does.

The rule is clear. Whenever the search goes below a node that is partly covered, it pushes that node first. The only nodes that do not push are the ones that stop the search: nodes that are outside the range, and nodes that are fully inside. Those two cases never look at their children, so they need no push.

Why the query is still O(log n)

The argument for the update is the same as the argument for the basic query. At each level only two nodes are partly covered, so only those two recurse. Every other node either stops at once or receives a note in one step. The push happens only on partly covered nodes, so pushes are also limited to about two per level.

The total work is therefore about 4 * log2(n) node visits, each with a constant amount of work. The range can be as long as the whole list and the answer is still found in logarithmic time.

Why the sum needs the length

The apply helper multiplies by the number of items. A common bug is to write self.sum[node] += v and forget the length. That adds v once to a node that covers several items. Consider the node [0..3] with sum 10 and note 0. A range add of 5 should make its sum 10 + 5 * 4 = 30. Adding just 5 gives 15, which is wrong. The fix is the factor r - l + 1.

The same reasoning applies to the note itself. The note lazy[node] is a per-item amount, not a total. When it is passed to a child, the child multiplies it by the child's own length inside _apply. That is why the note stores v and not v times the length.

Checking the lazy tree against a plain list

A lazy tree has more moving parts than the basic query, so it needs a stronger test than a single example. The best test is a plain list that does the same operations the slow way. The list is obviously correct, and the tree must agree with it after every step.

The next program does exactly that. It starts with fifty random values from a fixed seed. It then performs 300 random operations. Each operation is either an add on a random range, or a sum query on a random range. For each query, the program computes the answer with a slice sum over the plain list, and it compares that with the tree. It counts the checks and the matches.

The output is:

range sum checks: 128
matched: 128
first item now: 44

All 128 sum checks matched the plain list. The last line reads the first item after all the updates. The number depends on the random sequence, so a different seed or a different random generator gives a different number. What matters is that the checks match. If you change the lazy code and the last line changes, the updates behave differently, even if every check still matched.

The program uses random.Random(7). A seeded generator gives the same sequence every time, so the output is stable and you can compare it with a run on your own machine. The seed also makes a failing test reproducible, which matters when you debug. The separate Random object keeps the test from changing the state of any other code that uses the module-level generator.

The test covers the cases that break lazy code. Some operations cover a whole node and leave a note. Some cover a part of a node and force a push. Some queries read a node right after a note was applied above it. A single example like the one before the random test may not hit those paths, but three hundred random operations almost always do.

Debugging a lazy tree

When the random test fails, shrink the problem. Change n to 6 and the number of steps to 20, and print each operation and the tree's answer next to the plain list's answer. Stop at the first line where they differ. That line names the operation that broke, and you can trace it by hand against the dump above.

The usual causes are a missing push before a recursion, an apply that forgets the length, and a parent that is not recomputed after its children change. Check them in that order. The first is the most common in practice, because a missing push gives answers that look right until a query goes just below a stale node.

What happens inside Python

The lazy tree uses two lists of integers, sum and lazy. Each has 4 * n slots. A list of four million references takes about 32 megabytes, as the first lesson measured, so two such lists take about 64 megabytes before the int objects are counted. That is more than the basic tree, and the cost is worth knowing when you choose a structure. A lazy tree can also be stored with fewer slots by using an exact layout, but the simple 4 * n version is the one to learn first.

The calls use the same call stack as before. A push is an ordinary method call that applies two notes. Python runs it on the way down, before the children are used. Most of the time goes into the recursion itself, and in Python each function call has a noticeable cost. A tree over a million items makes millions of calls in a build, so the call overhead adds up. Measure before you rewrite it as a loop.

Python integers never overflow, so a long run of range adds cannot wrap a sum around. The price is that large integers take more memory and time than small ones.

Other lazy operations

The same idea supports other range updates, with more care about what a note means. Range assignment, which sets every item in a range to one value, uses a note that means "set everything below me to this value." A new assignment replaces any old pending assignment, so the note is simpler than an add note, but it must also overwrite the child's sum.

Range minimum with range add is a classic extension. When a note adds v to a node, the node's minimum also grows by v, because every item grew by v. So the apply helper adds v to the minimum as well as the sum. The push and the combine rules stay the same, and the minimum answers stay correct.

Each extension needs the same discipline. Define what the note means, make apply update every stored value that the note affects, and push before the recursion goes below a partly covered node. If any one of those three steps is missing, the answers are wrong without any error message.

Fenwick trees: a lighter alternative for sums

A Fenwick tree, also called a binary indexed tree, answers prefix sums and point updates. It uses one plain list, and each cell covers a block of items chosen by a bit trick. It is shorter to write than a segment tree, and it uses less memory. Its limit is that it is designed for operations that can be undone, such as sums, and it does not handle minimum or range assignment well.

The key expression is i & -i. It gives the lowest set bit of i, which is the largest power of 2 that divides i. For 6, written in binary as 110, the lowest set bit is worth 2, so 6 & -6 is 2. For 8, written as 1000, the lowest set bit is worth 8. Each cell bit[i] covers the i & -i items that end at position i.

Picture the blocks for a Fenwick tree over eight items. Positions are numbered from 1, and position p holds the item at list index p - 1. Cell 8 covers positions 1 to 8. Cell 6 covers positions 5 and 6. Cell 4 covers positions 1 to 4. Each cell covers the block that ends at its own position, and the block is as long as its lowest set bit.

Two loops do all the work. To add a value at a position, the update moves right: i += i & -i, which jumps to the next cell that covers this position. To get a prefix sum, the query moves left: i -= i & -i, which jumps to the next block that ends before this position. Each loop takes at most about log2(n) steps, because each jump clears or carries a bit.

The next program builds a Fenwick tree over the six values and prints a range sum. Then it adds 7 to one item and prints the same range sum again. The range sum of indexes 1 to 3 is computed as prefix(3) - prefix(0), which is the prefix up to index 3 minus the prefix up to index 0.

The output is:

15
22

The first answer is 3 + 5 + 7 = 15. After add(bit, 1, 7), the item at index 1 grows from 3 to 10, so the range sum becomes 10 + 5 + 7 = 22. The Fenwick tree changed one item and kept every prefix sum correct, using two short loops.

Notice the two loops. The add loop starts at position i + 1 and jumps forward, touching each block that includes the position. The prefix loop starts at position i + 1 and jumps backward, adding each block that ends before the position. The positions are shifted by one because the bit trick needs positions that start at 1, and Python lists start at 0.

The Fenwick tree stores only sums. Its prefix queries are fast, and range sums come from two prefixes. It cannot give the minimum of a range directly, because a block's minimum cannot be removed when a value changes. For that reason, a segment tree is the more flexible tool, and a Fenwick tree is the lighter tool for sums only.

Choosing between the two

A Fenwick tree and a segment tree both handle sums with point updates in O(log n). The Fenwick tree is shorter, uses about n slots instead of 4 * n, and has a tighter loop. The segment tree handles more operations. It can answer minimum, maximum and gcd, it can combine a range with any rule, and it supports lazy range updates.

A short rule helps. If the problem asks only for sums, with point changes and prefix or range sums, use a Fenwick tree. If it asks for a minimum, a maximum, a range add or a range assignment, use a segment tree. Mention both options in an interview, and say why you picked the one you did.

Common mistakes

Forgetting to push before recursing. The answers look right for simple cases and go wrong when a query reaches below a stale node. Push in both the update and the query, on every partly covered node.

Applying a note without the length. self.sum[node] += v is wrong for any node covering more than one item. The apply helper must multiply by r - l + 1.

Forgetting to recompute the parent after children change. After a recursive update, the node's sum must be rebuilt from its two children. Skipping that line leaves a stale sum above the change.

Mixing up the positions in a Fenwick tree. The Fenwick code uses positions that start at 1, while Python lists start at 0. Shifting by one at the boundary is easy to forget, and the error shows up as an answer that is off by one item.

Pushing a leaf. A leaf has no children, so the push must never run on a leaf. The standard code avoids this because a leaf is always fully covered or outside the range, and the search stops before a push. If you add special cases, check that a leaf never reaches the push.

Debugging walkthrough: a range add that is off by one item

Suppose a teammate reports that after add(2, 4, 5), the query query(4, 4) is 5 too small. Start with the smallest possible example. Build a tree over six items, add 5 to indexes 2 to 4, and query index 4 alone. Compare the answer with the plain list. If the answer is wrong, trace the path by hand. The root is partly covered, so it pushes. Then it recurses. The leaf at index 4 must receive the note from the node above it. If the note was never passed down, the push before the recursion is missing or the apply helper did not reach the leaf. Add the push, run the small example again, and the answer should match.

Notice how this differs from the earlier bugs. The leaf answer is wrong, but the root total may still look correct. That is the danger of lazy code: some answers are right, others are stale, and a total is not enough to show that the tree is correct. Check individual items as well.

Reading the true value from a lazy dump

A dump like the one above shows stored numbers, and stored numbers can be out of date. Learning to read them is a skill that saves time when you debug. The rule is simple. The true value of one item is the value stored at its leaf plus every pending note on the nodes above that leaf.

Check the rule on the dump. Index 0 is the leaf [0..0], which is node 8 and stores 1. Its ancestors are node 4, with note 0, and node 2, with note 10. So the true value is 1 + 0 + 10 = 11, which matches the list after the add. Index 1 is node 9, which stores 3. Its ancestors are node 4 (note 0) and node 2 (note 10), so its true value is 3 + 10 = 13. Index 4 is node 13, which stores 9. Its ancestors are node 6, node 3 and the root, and all three have note 0. So its true value is 9, which is correct, because index 4 was outside the update.

This rule explains why the query must push. A query reads stored values at the nodes it stops at, so every note above a stop must be delivered first. Otherwise the stored value at the stop is missing the notes above it, and the answer is short by exactly those notes.

What a range assignment changes

Range assignment sets every item in a range to one value. It is a different kind of lazy update, because the new value overrides the old values instead of adding to them. The note for an assignment says "every item below me is exactly this number." The sum of a node that receives the note is the number times its length.

The rules for combining notes follow from that meaning. When a node receives an assignment, any older add note on the same node is thrown away. The assignment overwrites every item below, so an add made before it no longer matters. When a node receives an add after an assignment, the add is combined with the assignment: the assigned value is increased by the add. A push then delivers that one combined assignment, so the children end with the right value.

A common mistake is to push the add before the assignment, or to keep both notes and apply them in the wrong order. Both give answers that are off by the old add. Keep one note per node, with a flag that says whether it is an assignment or an add, and define exactly what happens when a new note arrives. That definition is the design, and writing it down first saves a lot of debugging.

A checklist for any lazy tree

Use this checklist when you add a new lazy operation. Every item protects one of the rules above.

1. Write down what the note means in one sentence. For add, it is "every item below needs this much more." For assignment, it is "every item below is exactly this."
2. Write the apply step. It must update every stored value that the note changes. For add, that means the sum and the minimum, using the length for the sum.
3. Decide how a new note combines with an old note on the same node. Write the rule before you code it.
4. Push before recursing into any partly covered node, in both the update and the query.
5. Recompute the parent from its two children after every change below it.
6. Test with a plain list on random operations, with a fixed seed, and print the first step where the two disagree.

Explaining lazy propagation in two minutes

An interviewer may ask you to explain lazy propagation without code. A clear answer has four parts, and you can say it in about two minutes.

Start with the problem. A range update that touches every item costs O(n) if you update each leaf. Say that the goal is to make it O(log n).

Then the idea. When an update covers a whole node, do not visit the children. Update the node's sum, and leave a note that says the children still need the change. The note is a promise that is kept only when someone looks below the node.

Then the rule for reading. Before any operation goes below a partly covered node, push the note to its children and clear it. This keeps every child correct at the moment it is read.

Finish with the cost. Only partly covered nodes are pushed, and there are at most two per level, so the operation stays at O(log n). Mention the random test against a plain list, because it shows that you know how to check the code, not only how to write it.

Practice

1. Using the list [1, 3, 5, 7, 9, 11], what is query(0, 5) after add(0, 5, 1)? Hint: every item grows by 1.

Show the answer

The total grows by 6 items times 1, so the answer is 36 + 6 = 42. The new list is [2, 4, 6, 8, 10, 12], whose sum is 42. The root covers the whole range, so it is fully covered, and the search returns its sum directly after the apply.

2. Explain why the note in a node is passed to the children before the children are read, rather than when the update happens.

Show the answer

Passing the note at once would visit every leaf below the node, which costs O(n) for a large range. Keeping the note on the node means the work is done only for the nodes that a later query or update actually reads. The push runs on the way down, so the children are correct before anything reads them.

3. Compute 6 & -6 and 8 & -8 in binary. What do the results tell you about the blocks each Fenwick cell covers?

Show the answer

6 is 110 in binary, and -6 flips to ...010, so 6 & -6 is 010, which is 2. 8 is 1000, so 8 & -8 is 1000, which is 8. Cell 6 covers the 2 positions ending at 6 (positions 5 and 6), and cell 8 covers the 8 positions ending at 8 (positions 1 to 8).

4. A teammate writes the apply helper as self.sum[node] += v and self.lazy[node] += v. Give a small example where the answer is wrong, and show the correct result.

Show the answer

Take a node covering [0..3] with sum 10 and an add of 5 to the whole node. The correct sum is 10 + 5 * 4 = 30, because four items each grow by 5. The teammate's version gives 10 + 5 = 15, which is wrong. The fix is self.sum[node] += v * (r - l + 1).

5. The query pushes before it recurses. Describe a sequence of two operations where skipping the push in the query gives a wrong answer.

Show the answer

Start with a tree over four items. Call add(0, 3, 5), which applies a note of +5 to the root and leaves it pending. Then call query(0, 0). Without the push, the search goes down to the leaf at index 0 without the note ever reaching the children. The leaf still holds its old value, so the query returns the old item, which is 5 too small.

6. A node covers [4..9]. Using the rule that the node's note is applied to the left child and then the right child, give the ranges the children cover and the number of items each child gets.

Show the answer

The middle is (4 + 9) // 2 = 6. The left child covers [4..6], which has 3 items. The right child covers [7..9], which has 3 items too. Each child multiplies the note by its own item count inside _apply, so the left child grows its sum by 3 * v and the right child by 3 * v.

7. In a Fenwick tree over 8 items, which cells does the update add touch when the position is 3? Use the loop i += i & -i and start at position 3.

Show the answer

Start at position 3. 3 & -3 is 1, so the next position is 4. 4 & -4 is 4, so the next is 8. 8 & -8 is 8, so the next is 16, which is past the end of the list of size 9. The cells touched are 3, 4 and 8. Those are the blocks that cover position 3.

8. Write the Python lines for a Fenwick prefix query that returns the sum of the first k items, where k is a count and not an index. Use the prefix function from this lesson.

Show the answer

return prefix(bit, k - 1) when k is at least 1. The function prefix takes an index of the last item to include, so the first k items end at index k - 1. For k equal to 0, return 0 directly. The prefix function with index -1 also returns 0, but the direct return makes the empty case clear.

9. A teammate says lazy propagation is not needed because the Fenwick tree can also do range add. Explain why this is not enough for a range minimum query.

Show the answer

A Fenwick tree is built on sums that can be undone, so it can add a value to a position and remove it later. A minimum cannot be undone once a block has lost its smallest item, because the next smallest item is not stored anywhere in the cell. A lazy segment tree stores the minimum of each segment and updates it through the note, so it handles range add with minimum correctly.

What you now know

• A lazy note records a pending change at a node instead of visiting every item in a range. The note is passed down only when a later operation needs the children.
• Apply updates a node's sum with v * (r - l + 1) and adds v to the note. Push passes the note to both children and clears it.
• A range update and a range query both push on partly covered nodes, and they stop at nodes that are fully covered or outside the range. Both cost O(log n).
• A random test against a plain list, with a fixed seed, finds lazy bugs that a single example misses.
• A Fenwick tree stores block sums in one list and uses i & -i to walk blocks. It is shorter and smaller than a segment tree, but it handles sums only.

The next lesson is the module assignment. It combines point updates, range sums, range minimums and lazy range adds into one project.