Range assign and range add with lazy tags

Why it matters

Imagine a store that keeps the price of every item in a long list. Two kinds of updates arrive all day. One kind says "set every price from item 200 to item 399 to 0, because the shelf is cleared". The other says "add 5 to every price from item 1000 to item 1999, because of a tax change". Each update touches a long range. A plain segment tree would have to visit every item in the range, and that is slow when the range has a hundred thousand items.

The earlier lesson in this module on lazy propagation handled one kind of update, adding a value to a range. This lesson handles two kinds on the same tree: assign, which overwrites every value in a range with one number, and add, which adds one number to every value in a range. The hard part is not doing each update. The hard part is keeping the two kinds in the right order when they overlap, because "set to 7, then add 10" and "add 10, then set to 7" give different answers. The rest of this lesson builds the rules for that order, one step at a time.

A short reminder of lazy tags

A segment tree is a binary tree over an array. Each node stores the total of the values in its range. A lazy tag is a note on a node that says "this change still has to be passed to the children". The node's own total is already correct, so queries that stop at this node are fast. The children are updated only when the program needs to look inside them. That step is called pushing the tag down.

With add-only updates, one tag per node is enough. The tag is a number, and pushing it down means adding that number to each child. With assign and add together, one number is not enough, because the two changes behave differently. The next section shows why.

Two kinds of change

Take the array 1, 2, 3. Each kind of change does something different.

• Add 10 to all three values gives 11, 12, 13. Each value moves by the same amount, so the old values are still visible in the new ones.
• Assign 7 to all three values gives 7, 7, 7. Every old value is thrown away. Nothing about the old values can be recovered from the new ones.

This difference is what makes the tags tricky. An add tag only says "every value is 10 more than it was". A set tag says "every value is exactly this number, and everything before is gone". When both kinds sit on one node, the program has to keep track of which change happened last, and what it did to the values.

Why the order matters

Start with 1, 2, 3 again and apply the same two changes in two orders.

Order A: add 10, then assign 7.

• After add 10: 11, 12, 13.
• After assign 7: 7, 7, 7. The sum is 21.

Order B: assign 7, then add 10.

• After assign 7: 7, 7, 7.
• After add 10: 17, 17, 17. The sum is 51.

The two orders give different answers. So a tag must remember the changes in the order they arrived, and it must produce the same result as applying them one by one. The simple way to guarantee this is to follow one rule: a set tag wipes out any add tag that came before it, and an add tag that comes after a set tag is stored on top of the set.

The rules for one node

When a new change reaches a node, the node combines it with the tags it already holds. The table below shows the rules. "Set v" means every value is v. "Add d" means every value gets d more.

The third row is the rule that makes assign safe. A set overwrites the values, so an add that was waiting before it has no effect and can be thrown away. The fourth row shows how an add on top of a set is stored. The node still knows that its values came from v, and it adds d on top.

The program stores these two tags in separate arrays. set_v_ holds the set value, and has_set_ says whether a set is waiting. add_ holds the add amount. The fourth row means has_set_ is true, set_v_ is v, and add_ is d.

Pushing down in the right order

When a query or update needs to look inside a node, the node must pass its waiting tags to its two children. The node holds at most one set and one add. The set happened first, so it goes down first. The add happened after it, so it goes down second. Pushing the add first would be wrong. The children would receive the add, and then the set would overwrite the result of that add, and the add would be lost.

Here is the push step, taken from the program below.

void push(int node, int lo, int hi) {
    int mid = (lo + hi) / 2;
    int left_len = mid - lo + 1;
    int right_len = hi - mid;
    if (has_set_[node]) {
        applySet(2 * node, left_len, set_v_[node]);
        applySet(2 * node + 1, right_len, set_v_[node]);
        has_set_[node] = false;
    }
    if (add_[node] != 0) {
        applyAdd(2 * node, left_len, add_[node]);
        applyAdd(2 * node + 1, right_len, add_[node]);
        add_[node] = 0;
    }
}

The two if blocks must stay in this order. A later section shows what happens when they are swapped.

Applying a change to a node

Two small helper functions do the work for one node. Each one changes the node's total and its tags. The total is always correct after a helper runs, so a query that stops at this node can read the total directly. The helpers use ll, a short name for long long (a 64-bit integer type), which the full program below defines.

void applySet(int node, int len, ll v) {
    sum_[node] = v * len;
    has_set_[node] = true;
    set_v_[node] = v;
    add_[node] = 0;
}
 
void applyAdd(int node, int len, ll d) {
    sum_[node] += d * len;
    add_[node] += d;
}

The variable len is the number of values in the node's range. A node that covers 4 values has len equal to 4. So the total becomes v * len after a set, and sum_[node] + d * len after an add. The set clears add_ because the old add is no longer needed, which is the third row of the table. The add always goes into add_, which is the fourth and fifth rows.

Worked example: a five-value array

The program starts with the array 1, 2, 3, 4, 5. The sum is 15. It then runs four operations and prints the sum after each one. The operations use zero-based positions, so assign(2, 4, 7) covers the last three values.

Here is the sequence in plain words.

1. Add 10 to positions 1 to 3. The array becomes 1, 12, 13, 14, 5, with sum 45.
2. Assign 7 to positions 2 to 4. The array becomes 1, 12, 7, 7, 7, with sum 34.
3. Add -2 to position 3. The array becomes 1, 12, 7, 5, 7, with sum 32.
4. Query the sum of positions 1 to 3, which holds 12, 7, 5. The answer is 24.

The printed output of the program confirms each step. The code section below shows the program and its output.

The code

Here is the full program. It holds the tree, the two kinds of change, a sum query, and a random test that checks 300 arrays against a plain loop.

Compile and run it with these commands. The file is saved as lazy_tags.cpp.

g++ -std=c++20 -Wall -o lazy_tags lazy_tags.cpp
./lazy_tags

The program prints the following.

sum of all: 15
after add 10 to 1..3: 45
after assign 7 to 2..4: 34
after add -2 to 3: 32
sum of 1..3: 24
queries checked: 10016, mismatches: 0

The first five lines match the hand calculation in the worked example above. The last line says that all 10,016 queries in the random test returned the same sum as the plain loop.

A second example: overlapping ranges

Now take a harder case. The array is 1, 2, 3, 4, 5 again. First assign 7 to positions 0 to 2. Then add 1 to positions 1 to 4. The two ranges overlap at positions 1 and 2.

After the assign, the array is 7, 7, 7, 4, 5. The sum of positions 0 to 4 is 30. The program confirms this.

The add covers positions 1 to 4. Position 1 and position 2 hold 7 from the assign, so they become 8. Positions 3 and 4 become 5 and 6. The array is 7, 8, 8, 5, 6, and the sum is 34.

The sums printed by the program for this sequence are these.

assign 7 to 0..2, sum 0..4: 30
add 1 to 1..4, sum 0..4: 34
sum 1..2: 16
sum 3..4: 11

The sum of positions 1 to 2 is 8 + 8 = 16, and the sum of positions 3 and 4 is 5 + 6 = 11. The program finds the same numbers.

The overlap is where the rule about pushing matters. The root covers positions 0 to 4, and the add covers only part of that, so the program pushes the root's tags down and goes into its children. The left child covers positions 0 to 2 and holds the set of 7 from the assign. The push gives that set to its two children first. Then the add reaches positions 1 and 2, and each of them becomes 8. Position 0 is outside the add range, so it keeps the 7 it received from the set.

A third example: three changes in a row

The third example starts with the array 5, 5, 5, 5 and uses three changes. Each change leaves a different mix of tags behind, so it tests the table of rules.

1. Add 3 to position 0. The array becomes 8, 5, 5, 5. Position 0 now has an add tag, and the node above it has no tag.
2. Assign 1 to positions 0 and 1. The array becomes 1, 1, 5, 5. The set wipes out the add that was waiting on position 0.
3. Add 2 to positions 1 to 3. The array becomes 1, 3, 7, 7. Position 1 now sits under a set that has an add on top of it, which is the fourth row of the table.

The program prints the sums after each step.

add 3 to 0..0, sum 0..3: 23
assign 1 to 0..1, sum 0..3: 12
add 2 to 1..3, sum 0..3: 18
sum 2..3: 14

The sums are 8 + 5 + 5 + 5 = 23, then 1 + 1 + 5 + 5 = 12, then 1 + 3 + 7 + 7 = 18. The last query covers positions 2 and 3, which hold 7 and 7, so the answer is 14.

Common mistakes

Mistake 1: pushing the add before the set. This is the mistake the push step guards against. Swap the two if blocks in push, so the add is applied first and the set second, and run the same random test. The real run printed this.

queries checked: 10016, mismatches: 2798

The count is high because the two orders disagree on almost every node that has both tags. The add is applied to the children, and then the set overwrites those children with a fixed value. The add is lost, and later queries read the wrong sums.

Mistake 2: not pushing before a partial update. A node that is only partly inside the update range must push its tags before its children are changed. Without the push, a child can be changed while the parent still holds a waiting set. The later push then overwrites the change. Delete the push call from addRange and nothing else, and run the same random test. The real run printed this.

queries checked: 10016, mismatches: 3220

The fix is to call push(node, lo, hi) before the recursive calls, as the code above does in each of the three range functions.

Mistake 3: forgetting to clear the add when a set arrives. If applySet does not reset add_ to zero, an old add stays on the node. When the set is pushed down, the children get the set, and then they get the old add on top of it. The result is wrong by that old amount. This is the third row of the table. The line add_[node] = 0; in applySet is there for this reason.

Mistake 4: a compile error from a call with too few arguments. Every update takes a left end, a right end, and a value. A call that leaves out the value stops the compiler with a message like this one. The message below comes from a small test file that has the same assign signature as the program.

bad_call.cpp: In function 'int main()':
bad_call.cpp:9:16: error: no matching function for call to 'LazySum::assign(int, int)'
    9 |     tree.assign(2, 4);
      |     ~~~~~~~~~~~^~~~~~
bad_call.cpp:9:16: note: there is 1 candidate
bad_call.cpp:5:10: note: candidate 1: 'void LazySum::assign(int, int, long long int)'

The fix is to pass all three arguments: tree.assign(2, 4, 7);.

Mistake 5: wrong length for a node. The set and add helpers use len to scale the total. For a node with range lo to hi, the length is hi - lo + 1. The left child of a node with range lo to hi has length mid - lo + 1, and the right child has length hi - mid. Using the parent's length for a child gives totals that are too large.

Practice

Exercise 1. The array is 1, 2, 3. Apply add 10 to all values, then assign 7 to all values. What is the final array, and what is its sum?

Show the answer

After the add the array is 11, 12, 13. The assign then replaces every value with 7, so the array is 7, 7, 7. The sum is 21. The assign wipes out the add, which matches the third row of the table.

Exercise 2. The array is 1, 2, 3 again. Apply assign 7 to all values, then add 10 to all values. What is the final array, and what is its sum?

Show the answer

After the assign the array is 7, 7, 7. The add then gives 17, 17, 17. The sum is 51. The add stays on top of the set, which matches the fourth row of the table.

Exercise 3. A node covers four values. Its tags are set 5, and then add 2 arrives on the node. What tags does the node hold, and what is the sum of the node?

Show the answer

The node holds set 5 with add 2 on top. Each of its four values is 7, so the sum is 7 * 4 = 28. The program would store set_v_ as 5, add_ as 2, and has_set_ as true. The sum is 5 * 4 from the set plus 2 * 4 from the add.

Exercise 4. A node holds an add of 4. Then a set to 1 arrives on the node. What happens to the add?

Show the answer

The set overwrites every value under the node, so the add of 4 has no effect on the final values. The rule in the third row of the table says the add is dropped. The node now holds only the set to 1. The program does this in applySet, where add_[node] is set back to 0.

Exercise 5. A node covers positions 0 to 4 and has a waiting set of 3. Its left child covers positions 0 to 2, and its right child covers positions 3 and 4. When the node is pushed down, what does each child receive, and what is the sum of each child after the push?

Show the answer

The left child covers 3 values, so it receives set 3, and its sum becomes 3 * 3 = 9. The right child covers 2 values, so it receives set 3, and its sum becomes 3 * 2 = 6. The len value passed to each child is the length of that child's range, which is why the split uses mid - lo + 1 for the left child and hi - mid for the right child.

Summary

• A set tag overwrites every value in a node's range. An add tag adds the same amount to every value in the range.
• Changes must be applied in the order they arrived. A set wipes out an earlier add, and an add after a set is stored on top of the set.
• A node can hold one set tag and one add tag. The set is older, so it is pushed to the children first, then the add.
• Push a node's tags before any update or query looks inside its children. Skipping the push gives wrong sums.
• Each node's total must be updated by its length, which differs between the parent and the children.