Arrays and searching 0/121

Segment trees for range queries and updates · 3 of 3 Advanced

Lazy propagation

Update a whole range at once by leaving tags on the nodes inside it and pushing them down only when an operation goes below.

2,257 words · 11 min read

Part 1 of 5 Range updates

Add to every value in a range

So far, an update has changed one value. A range update changes every value in a range at once, such as "add 3 to positions 2 to 7". A Fenwick tree over a difference array handles range additions when each question is about a single position. Here both the update and the question are about ranges: add to a range, and ask for the sum of a range.

Take the same eight values as on the earlier pages, this time in a tree of sums:

24[0, 8)14[0, 4)5[0, 2)3[0, 1)2[1, 2)9[2, 4)4[2, 3)5[3, 4)10[4, 8)2[4, 6)1[4, 5)1[5, 6)8[6, 8)5[6, 7)3[7, 8)
Each node holds the sum of the range written under it.

The direct way to add 3 to the range [2, 8) is six point updates, one for each position. In general that is up to nn point updates of O(log⁡n)O(\log n) steps each for one range update, slower than writing the nn values into a plain array. With 200,000 range updates on 200,000 values, it comes to 4×10104 \times 10^{10} leaves to change.

A range query never visits every leaf of its range. It stops at the nodes that are inside the range, here [2, 4) and [4, 8), because each of them already holds the answer for everything below it. A range update can stop at the same nodes, provided it does two things at each of them:

  1. It corrects the node's own sum. Every value below the node grows by 3, so the sum grows by 3 times the length of the node: [2, 4) goes from 9 to 9+3×2=159 + 3 \times 2 = 15, and [4, 8) goes from 10 to 10+3×4=2210 + 3 \times 4 = 22.
  2. It leaves a note on the node saying that everything below still has to receive +3+3. This note is called a lazy tag, or just a tag.

The nodes above them, which are only partly inside the range, are recomputed from their children as in a point update: [0, 4) becomes 5+15=205 + 15 = 20 and the root becomes 20+22=4220 + 22 = 42. A direct count agrees, since six values grew by 3 and 24+6×3=4224 + 6 \times 3 = 42.

The tree after adding 3 to [2, 8). The two tagged nodes and the nodes above them are correct. The faded nodes below the tags still hold their old sums.

Some nodes of the tree are now out of date, which has not happened on the earlier pages. It is safe because of where they are. Every node from the two tagged ones upward holds the correct sum, so a query that stops at or above them is answered correctly: the sum of the whole array is 42, and the sum of [4, 8) is 22. The out-of-date nodes all lie below a tag, and the tag records what they are missing. So a tagged node's own sum is up to date, and its tag is what its children have not received yet.