Lazy propagation and the Fenwick tree

Why it matters

So far every update has changed one element. Many real problems change a whole run of elements at once. A store adds a discount to every product in a category. A game gives every player in a level group a bonus. A sensor applies the same calibration to a range of readings. Doing that one element at a time costs O(n) per update, which is the same slow cost we measured in lesson 1. This lesson shows two ways to make range changes cheap. The first is lazy propagation, a segment tree trick that delays work until it is needed. The second is the Fenwick tree, a shorter structure that handles prefix sums and point updates with about ten lines of code.

The range update problem

Take the array {2, 4, 1, 7, 3} and suppose the operation is "add 10 to every element from index 1 to index 3". The new array is {2, 14, 11, 17, 3}. A plain loop does three writes, which is fine here. On an array of a million elements with a range of half a million, the loop does half a million writes for one update, and a stream of such updates becomes too slow.

A segment tree can do better, but only if we avoid visiting every leaf. The idea is to apply the change to whole nodes. If a node's segment lies completely inside the update range, we change the node's stored answer once and stop. We do not walk down to its leaves. The leaves below it stay stale, and that is the problem lazy propagation solves.

For sums, adding v to every element of a node covering len elements raises the node's sum by v * len. A node covering 4 elements with sum 20 becomes 20 + 4 * 10 = 60 after adding 10 to each element. The node gets the right answer immediately, with one multiplication.

The lazy tag

Lazy means "do the work later". When an update covers a whole node, we do two things. We fix the node's own stored answer. Then we leave a note on the node, called the lazy tag, that says "my children still owe this addition". The children are not touched yet.

The note is pushed down only when a later operation needs to look inside the node. A query or an update that must reach the children first pushes the tag: it adds the tag to each child's answer and sets each child's own tag, then clears the parent's tag. After that, the children are correct and the parent has no debt.

The idea is like a manager who announces "everyone gets a 10-dollar bonus this month" and writes it on the board. Nobody's pay changes until someone asks about one person's pay. Then the team lead tells that person the bonus, and the note is passed down one level. The manager's total is already right, because the manager knows the bonus applies to the whole team. Only the detail is delayed.

The rule that makes this safe is simple. A node's own stored answer is always correct, even while its tag is waiting. Only its children can be stale, and the tag says by how much. Every operation that reads or changes the children must push first.

Here is the apply and push pair for a sum tree. apply changes a node by a value v across its whole segment. push hands the parent's pending tag down one level.

void apply(int node, int l, int r, long long v) {
    t[node] += v * (r - l + 1);   // the node's own total is correct now
    lz[node] += v;                // the children still owe v
}
 
void push(int node, int l, int r) {
    if (lz[node] == 0) return;
    int mid = (l + r) / 2;
    apply(2 * node, l, mid, lz[node]);
    apply(2 * node + 1, mid + 1, r, lz[node]);
    lz[node] = 0;                 // the debt has been passed down
}

Two details matter. apply uses r - l + 1, the length of the node's segment, so the total is right even for an uneven split. push uses the same midpoint as the build, so each child's segment matches the segment it was built for.

What the push looks like

The picture below shows one push on a small example. The array is {2, 4, 1, 7, 3}, and the update is add(0, 2, 10), which adds 10 to indexes 0, 1 and 2. Node [0..2] sums to 7 before the update and 37 after it, because 7 + 3 * 10 = 37. Its children are [0..1] with sum 6 and [2] with sum 1. Those children are stale, because the tag has not been pushed yet.

Before and after a lazy push. The parent node [0..2] keeps its sum 37 with the note moved down to its children, which become 26 with a note and 11.

When a later query goes into node [0..2], the push runs. The child [0..1] covers two elements, so it gains 2 * 10 = 20 and becomes 26. The child [2] covers one element, so it gains 10 and becomes 11. Both children now carry their own notes, which the next push will pass down further. The parent's note is cleared, and its sum of 37 was right all along.

Worked example 1: lazy range add and range sum

The next program is a complete lazy segment tree. It supports two commands. a l r v adds v to every element from l to r. s l r prints the sum from l to r. Type the input into the Input box and run it.

Input, one item per line:

5
2 4 1 7 3
4
s 0 4
a 1 3 10
s 0 4
s 2 3

Expected output:

17
47
28

Trace it. The first query s 0 4 covers the whole array, so the root answers 17 at once. The sum of {2, 4, 1, 7, 3} is 17, which is correct. The command a 1 3 10 adds 10 to indexes 1, 2 and 3. The root covers [0..4] and is only partly inside the update, so it asks its children. The node [0..2] is partly inside: index 0 is outside, and indexes 1 and 2 are inside. The node [0..1] is partly inside, so it asks its children. The leaf [0..0] is outside, and the leaf [1..1] is fully inside, so it gets 10 added. The leaf [2..2] is fully inside too, and it gets 10. The node [3..4] is partly inside, so index 3 gets 10 and index 4 is outside. The total change is 3 * 10 = 30, so the array sums to 47.

The second s 0 4 covers the whole array, so it reads the root, which already holds 47, and prints 47. The last command s 2 3 walks down through the partial nodes. Each partial node pushes its tag before its children are read. Here the earlier add left the values at 2 and 3 already correct, so the pushes change nothing, but the query follows the rule anyway. The values at 2 and 3 are 11 and 17, and their sum is 28.

Notice that every answer is right because each node's own total is always up to date. Only a node's children can be stale, and a push fixes them before they are read.

The Fenwick tree

Lazy propagation handles range updates and range queries, but it is more code than we need when the question is simpler. Often the question is only a prefix sum: "what is the total of indexes 0 to i?" combined with point updates, where one element changes at a time. For that case there is a much shorter structure called the Fenwick tree, also known as a binary indexed tree. It uses one array and about ten lines of code, and both operations take O(log n).

The key idea is in the name of its operator, i & -i. This expression gives the lowest set bit of i, which is the value of the rightmost 1 in the binary form of i. In binary, 6 is 110, and its lowest set bit is 10, which is 2. In binary, 12 is 1100, and its lowest set bit is 100, which is 4. The value i & -i is the size of the block a Fenwick slot covers.

Here is the rule. Slot i of a Fenwick tree stores the sum of the i & -i elements that end at position i, counting in the 1-based way the tree uses internally. Slot 4 covers 4 elements, positions 1 to 4. Slot 6 covers 2 elements, positions 5 and 6. Slot 5 covers one element, position 5. The picture below shows the blocks for eight slots.

Fenwick blocks for eight slots. Each slot covers a block of items that ends at its position, and the block length is the lowest set bit of the slot number.

With this layout, a prefix sum is a short walk. To get the sum of positions 1 through i, start at i and add the stored block. Then jump down by removing the lowest set bit, i -= i & -i, and add the next block. Each jump removes one set bit, so the walk takes at most as many steps as there are 1 bits in i, which is at most about log2 n.

An update works in the opposite direction. To add a value at position i, start at i and add it to the slot. Then jump up by adding the lowest set bit, i += i & -i, and add it to the next slot that covers i. Each jump up also adds one set bit, so the walk stops after about log2 n steps.

Here is the whole structure in C++:

struct Fenwick {
    int n;
    vector<long long> f;
    Fenwick(int n) : n(n), f(n + 1, 0) {}
    void add(int i, long long d) { for (i++; i <= n; i += i & -i) f[i] += d; }
    long long prefix(int i) const {  // sum of 0..i
        long long s = 0;
        for (i++; i > 0; i -= i & -i) s += f[i];
        return s;
    }
    long long range(int l, int r) const {
        return prefix(r) - (l > 0 ? prefix(l - 1) : 0);
    }
};

The i++ in add and prefix converts the outside index, which starts at 0, to the internal index, which starts at 1. Without it the lowest set bit of 0 is 0, and the loop would never move. That one line is the most common source of bugs in a Fenwick tree.

Worked example 2: a Fenwick tree with point updates

The next program uses a Fenwick tree for the same array as before. The commands are s l r for a range sum and a i d, which adds d to one element. Note that this command changes one element, so a Fenwick tree is enough.

Input, one item per line:

5
2 4 1 7 3
3
s 1 3
a 2 9
s 1 3

Expected output:

12
21

The Fenwick tree is built one element at a time, with add(i, a[i]) for each value. That costs O(n log n) in total, which is slower than the O(n) build of a segment tree, but it is simple and fast enough for most inputs. The first query s 1 3 is prefix(3) - prefix(0). The call prefix(3) reads slot 4, which holds the four values 2, 4, 1, 7, and then stops at 0, since 4 minus its lowest bit is 0. So prefix(3) is 14, and the answer is 14 - 2 = 12.

The command a 2 9 adds 9 to position 2, which changes 1 into 10. The Fenwick tree updates the slots that cover position 2, which are slots 3 and 4, and the next jump is past the end of the array. The second query gives 4 + 10 + 7 = 21, which is correct.

Worked example 3: count inversions with a Fenwick tree

A Fenwick tree is more than a prefix-sum tool. It can count things. Here is a classic interview problem. An inversion is a pair of positions i < j where a[i] > a[j]. The array {2, 3, 8, 6, 1} has the inversions (2, 1), (3, 1), (8, 6), (8, 1) and (6, 1), which is 5 in total. Checking every pair takes O(n squared) work. A Fenwick tree does it in O(n log n).

The method goes through the array from left to right. For each value, count how many earlier values are greater than it. Those earlier values are the inversions it creates. The Fenwick tree stores how many values have been seen for each value, so the count of earlier values that are greater is "earlier values so far, minus earlier values that are at most this value". The values can be large, so the program first replaces each value by its rank, its position in the sorted list of distinct values. Ranks are small, and the Fenwick tree needs only as many slots as there are distinct values.

Input, one item per line:

5
2 3 8 6 1

Expected output:

5

Trace the first three values. The value 2 is first, with no earlier values, so it adds 0 inversions. The value 3 is second. There is one earlier value, 2, which is not greater than 3, so it adds 0. The value 8 is third. The two earlier values, 2 and 3, are both smaller, so it adds 0. The value 6 is fourth. The earlier values are 2, 3 and 8. Only 8 is greater than 6, so it adds 1, and the formula gives 3 - (number of earlier values at most 6) = 3 - 2 = 1. Finally the value 1 is last. All four earlier values are greater, so it adds 4, and the total is 5.

Now the second test. Type 4 and then 3 3 1 1 into the Input box. The expected output is 4, because the pairs (3, 1) appear four times: both 3s are before both 1s. Equal values do not count as inversions, so there are no inversions among the two 3s or among the two 1s. This is the edge case most learners get wrong on their first try, and the formula handles it because countUpTo counts values that are at most a[i], including equal ones.

Worked example 4: range add with point queries

The last example uses the Fenwick tree in another way. Suppose we need to add a value to a whole range, but we only ever ask for single values. A difference array solves this. To add v to indexes l through r, we add v at position l and -v at position r + 1 of a separate array d. The value at any index i is its base value plus the prefix sum of d up to i. The prefix sum of d goes up by v at l and comes back down by v at r + 1, so exactly the indexes from l to r see the extra v.

We store the difference array in a Fenwick tree, so both the range add and the point query take O(log n). The program below uses the commands a l r v and g i. The g command prints the current value at one index.

Input, one item per line:

5
2 4 1 7 3
5
a 1 3 10
g 2
a 0 0 -5
g 0
g 4

Expected output:

11
-3
3

Trace it. The base array is {2, 4, 1, 7, 3}. The command a 1 3 10 adds 10 at position 1 and -10 at position 4 in the difference Fenwick tree. The command g 2 computes the value at index 2. The base value is 1. The prefix sum of the difference array up to index 2 includes the +10 at position 1 and nothing from position 4, so it is 10. The answer is 1 + 10 = 11.

The command a 0 0 -5 adds -5 at position 0 and +5 at position 1. Now g 0 has base 2 and prefix sum over positions 0 through 0, which is -5, so the answer is -3. Negative values are allowed, and the program prints them without any special case. The last query g 4 has base 3. The prefix sum up to 4 includes the +10 at position 1, the -10 at position 4, and the -5 and +5 from the second add. These cancel as expected, and the total is 0, so the answer is 3, the original value.

This is the third way to handle a range update, and it is the simplest when queries are single points. If you need range sums as well, lazy propagation or a pair of Fenwick trees is the right tool.

Choosing the right structure

Each structure fits a different set of questions. The table below is a quick guide, and it matches the choices an interviewer expects you to justify.

The rule that ties them together is the one from lesson 1. Prefix sums need subtraction. A Fenwick tree needs subtraction too, because it removes the part before a range. A segment tree needs only an associative operation and a neutral value. So if the operation is min or max, you cannot use a Fenwick tree for ranges, and the segment tree is the answer.

What happens inside

The lazy tree costs O(log n) per operation in the normal case. An update visits the partial nodes on two paths, one for each end of the range. At each partial node it pushes, which is constant work. The total is O(log n) nodes, with a few constant operations at each one.

The lazy tree needs two arrays of 4n slots, one for the sums and one for the tags. That is twice the memory of a plain segment tree. For the usual sizes it is still small, but it is worth knowing when you judge a solution.

The Fenwick tree needs one array of n + 1 slots. Each prefix walks at most about log2 n slots, and each update walks at most about log2 n slots. The loops are very short and the memory access is simple, so Fenwick trees are fast in practice. That speed is one reason competitive programmers reach for them first.

The difference-array trick costs two Fenwick updates per range add. That is still O(log n), so a range add is as cheap as a point update, and no structure needs to store the full array of sums.

Why a Fenwick walk takes log n steps

The claim that a Fenwick prefix takes about log n steps can be checked by counting. Each step of prefix(i) removes the lowest set bit of the working index. So the number of steps equals the number of 1 bits in the index, plus one for the final check. Take prefix(6). Internally the index is 7, which is 111 in binary, and the walk visits 7, then 6, then 4, then stops at 0. That is three steps for three 1 bits. Take prefix(7), whose internal index is 8, which is 1000 in binary. The walk visits 8 and stops at 0: one step, because there is one 1 bit.

The worst case is an index whose binary form is all 1s, such as 7 or 15 or 31. Each of those has as many 1 bits as its length, and the length of an index near n is about log2 n. So the walk never takes more than about log2 n steps, and it usually takes fewer, because most indexes have a mix of 0s and 1s. Updates work the same way in reverse: each step adds the lowest set bit, which sets one more bit, so the walk ends after about log2 n steps as well.

This argument is the reason the Fenwick tree is both short and fast. It has no tree of nodes to allocate, no recursion, and no tags. The only work is bit arithmetic on one index, and bit arithmetic is one of the fastest things a processor does.

Choosing between lazy propagation and a Fenwick tree

Once you know both structures, the choice is a short list of questions. Ask whether the operation is a point change or a range change. If it is a point change and the query is a prefix or range sum, use a Fenwick tree, because it is shorter and faster. If the operation is a range change, the query is a sum, and the operation has an inverse, a Fenwick tree over a difference array can still help, but you need two Fenwick trees for a general range add with range sum. Lazy propagation is the simpler choice there, because one structure covers both. If the query is a minimum or maximum, use a segment tree, with lazy tags only if the updates are ranges.

Suppose a game stores one score per player and needs two things: add points to a range of players at once, and ask for the total score of a range. The range add changes many players, and the query is a sum, so lazy propagation is the natural fit. Now suppose the same game only ever awards points to one player at a time and asks for the total of the first k players. That is a point update and a prefix sum, so a Fenwick tree is shorter and just as fast.

The question to answer out loud, in an interview or a design review, is "what changes, and what is asked?" Once the answer is clear, the structure follows.

Common mistakes

Forgetting to push before recursing. In a lazy tree, a query or update that goes into the children must push the parent's tag first. Without it, the children are stale and the answer is wrong. The bug is silent. Some answers look right by chance, which makes the bug hard to find.

Forgetting to recompute the parent after a recursive add. The parent's total must be rebuilt from its children after they change. The debugging walkthrough below shows what happens when the line is missing.

Forgetting the i++ in a Fenwick tree. Positions start at 0 outside the tree and at 1 inside it. If the code uses i directly, the lowest set bit of 0 is 0, and the loop never moves. The result is either a wrong answer or a program that hangs.

Pushing on a leaf. A leaf has no children. Pushing from a leaf writes to slots that belong to other nodes. A correct lazy tree never pushes on a leaf, because a leaf is always either fully inside the range or fully outside it, and neither case pushes.

Using int after many range adds. Each add can raise a total by v times the segment length. After thousands of adds the total is far above the int limit. Use long long for the tree and the tags.

Mixing up the difference array's end. For the range add, the -v goes at r + 1. A learner who writes r puts the cancellation inside the range, and every value in the range is wrong by v except the last one.

Debugging walkthrough: a lazy tree with a stale total

A learner adds the recompute line in add and then removes it while testing. The program still compiles, and the learner runs the same commands as the worked example: s 0 4, a 1 3 10, s 0 4, s 2 3. The expected output is 17, 47, 28. The actual output is:

17
17
28

The second answer is wrong. The sum over the whole array should be 47, but the program prints 17. The third answer, for [2, 3], is still correct. That pattern is a clue. The whole-array query uses the root directly, because the root is a full overlap. The root's total was never recomputed after the add, so it still holds 17. The query for [2, 3] goes down and reads the children, which were pushed correctly, so it gives 28.

The learner's fix is the same as the one in the code: restore t[node] = t[2 * node] + t[2 * node + 1]; at the end of add. The method to remember is this. When one query is wrong and another is right, look at which nodes each query used. If the wrong answer came from a node that the right answer did not use, the bug is in that node's stored value.

Variations and edge cases

A range add with l equal to r is a single-element update. The lazy tree handles it, but a point update in a Fenwick tree is shorter.

A range that covers the whole array makes the root a full overlap, so the query returns at once without pushing. Test this case, because it is the only time some stale values are hidden.

A negative value added to a range works the same as a positive one. The tags and sums are signed, so the arithmetic is the same.

A Fenwick tree over a single element works, and the loop for (i++; i <= n; ...) runs once. Check it with n = 1 as you would for the segment tree.

Duplicates matter for the inversion count. Equal values do not form an inversion, and the countUpTo formula counts equal earlier values as "not greater", which is exactly right.

Interview-style questions

"How would you support range add and range sum?" Answer: a lazy segment tree. Each node keeps its sum and a pending tag, the update applies the tag to whole nodes, and the tags are pushed down only when a later operation needs the children. Each operation is O(log n).

"Why not use a Fenwick tree for range minimum?" Answer: a Fenwick tree needs subtraction to remove the part before a range. A minimum has no inverse, so the trick fails. A segment tree needs only the operation and a neutral value.

"How do you count inversions in O(n log n)?" Answer: replace values by ranks, then go left to right. For each value, count the earlier values that are greater, using a Fenwick tree over ranks. Add the value after counting.

"Why does i & -i appear in a Fenwick tree?" Answer: it gives the size of the block that slot i covers, and it lets the prefix walk remove one set bit per step and the update walk add one set bit per step. Both walks take about log n steps.

Practice

1. Using the lazy tree on {2, 4, 1, 7, 3}, add 5 to the whole array and then print sum(0, 4). The expected answer is 42. Explain how the root's total changes.
2. Compute i & -i for 6, 8 and 12 by hand. Check your answers with a quick program that prints them.
3. Which structure would you use for "range minimum with point updates"? Give one reason it is better than a Fenwick tree.
4. Use the Fenwick tree from worked example 2 on {1, 2, 3, 4}. Then add 5 at position 1 and print the range sum from 1 to 2. Work it out before you run the program.
5. Explain why prefix(i) takes at most about log2 n steps. Use the fact that each step removes one set bit.
6. In the lazy tree, why must sum push before it reads the children, even though push is not needed for the root's own answer?
7. Change the inversion program so that it counts pairs i < j with a[i] < a[j]. Which single line changes, and why?
8. Explain why the range sum from l to r in a Fenwick tree is prefix(r) - prefix(l - 1). What is special about l = 0?
9. Using the difference-array program on base array {2, 4, 1, 7, 3}, the commands are a 0 4 7, then a 2 2 -7, then g 2. What is printed? Work it out by hand.
10. Describe in plain words why a Fenwick tree cannot answer range minimum queries, and say what kind of tree can.

What you now know

• A range update can be cheap if whole nodes take the change and their children are updated later.
• A lazy tag is a note saying what the children still owe. The node's own answer is always correct.
• Push the tag down before reading or changing the children, and never push from a leaf.
• A Fenwick tree stores blocks that end at each slot, and i & -i sets the block size.
• The Fenwick prefix walk removes one set bit per step, and the update walk adds one.
• A Fenwick tree works for sums and their inverses. It does not work for min or max.