29.04Intermediate / Advanced6 topics18 min6 interactive animations

Lazy propagation

Lazy propagation lets a segment tree apply an update to a whole range in O(log n) by leaving a tag on fully covered nodes and handing it down only when needed.

Learning goals

Apply a range add without touching every leaf
Apply a range assignment and keep sums correct
Describe a lazy tag and when it is pushed down
Compose tags so that mixed updates stay correct

Prerequisites

Segment tree fundamentalsRecursion

Painting a fence one board at a time is slow. Painting a whole section and leaving a note 'this section is painted red' is fast, and you only repaint boards individually when someone asks about one of them. A lazy tag is that note.

29.04.1

Range addition

To add v to every element of a[l..r] without visiting every leaf, stop at the nodes fully inside [l, r]. For such a node, fix its own sum at once (sum += v × length) and store v as a pending **tag**, meaning 'every element below still has to receive v'. The children are not touched. A node only partly covered must first push its tag down, then recurse and recompute its sum from its children.

Run the preset "Add, then sum" (+0:5:3 ?2:6 on 1..8): the add stops at fully covered nodes, the later sum query pushes one tag down, and the answer for positions 2..6 is 37 (the values are 6 7 8 9 7). The statistics panel shows 14 node visits and 1 push-down.

Java

1static long[] sum, tag;                          // tag[node]: an add the children have not received yet
2static int[] a;
3static void init(int[] values) {
4    a = values;
5    sum = new long[4 * a.length];
6    tag = new long[4 * a.length];
7    build(1, 0, a.length - 1);
8}
9static void build(int node, int lo, int hi) {
10    if (lo == hi) { sum[node] = a[lo]; return; }
11    int mid = lo + (hi - lo) / 2;
12    build(2 * node, lo, mid);
13    build(2 * node + 1, mid + 1, hi);
14    sum[node] = sum[2 * node] + sum[2 * node + 1];
15}
16static void apply(int node, int len, long v) { sum[node] += v * len; tag[node] += v; }
17static void push(int node, int lo, int hi) {     // hand the pending add to the children
18    if (tag[node] == 0) return;
19    int mid = lo + (hi - lo) / 2;
20    apply(2 * node, mid - lo + 1, tag[node]);
21    apply(2 * node + 1, hi - mid, tag[node]);
22    tag[node] = 0;
23}
24static void rangeAdd(int node, int lo, int hi, int l, int r, long v) {
25    if (r < lo || hi < l) return;
26    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, v); return; }   // fully covered: stop, lazily
27    push(node, lo, hi);
28    int mid = lo + (hi - lo) / 2;
29    rangeAdd(2 * node, lo, mid, l, r, v);
30    rangeAdd(2 * node + 1, mid + 1, hi, l, r, v);
31    sum[node] = sum[2 * node] + sum[2 * node + 1];
32}
33static long query(int node, int lo, int hi, int l, int r) {
34    if (r < lo || hi < l) return 0;
35    if (l <= lo && hi <= r) return sum[node];
36    push(node, lo, hi);
37    int mid = lo + (hi - lo) / 2;
38    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
39}

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(n)

Lazy propagation: range add, range assign, range sum

Interactive · edit the input

segment tree: node value = sum of its range; a pending tag is shown after the range (+v add, =v assign) · 15 nodes

[0,7]

[0,3]

[0,1]

[0,0]

[1,1]

[2,3]

[2,2]

[3,3]

[4,7]

[4,5]

[4,4]

[5,5]

[6,7]

[6,6]

[7,7]

Partly inside: push down, recurseFully inside: tag itTag handed down / recomputedOutside

true values a[] (what the tree represents)

Setup

A range update would touch O(n) leaves. Lazy propagation stops at the nodes fully covered by the range, fixes their sums at once and leaves a tag saying what the children still owe. The tag is pushed down only when a later operation needs the children.

Step 1 / 22

Java

1void apply(int node, int len, int kind, long v) {            // put a tag on node
2    if (kind == SET) { sum[node] = v * len; tagKind[node] = SET; tagVal[node] = v; }
3    else {                                                   // ADD
4        sum[node] += v * len;
5        if (tagKind[node] == NONE) { tagKind[node] = ADD; tagVal[node] = v; }
6        else tagVal[node] += v;                              // ADD after ADD or after SET: just add to the value
7    }
8}
9void push(int node, int lo, int hi) {                        // hand the pending tag to the children
10    if (tagKind[node] == NONE) return;
11    int mid = lo + (hi - lo) / 2;
12    apply(2 * node, mid - lo + 1, tagKind[node], tagVal[node]);
13    apply(2 * node + 1, hi - mid, tagKind[node], tagVal[node]);
14    tagKind[node] = NONE;
15}
16void rangeUpdate(int node, int lo, int hi, int l, int r, int kind, long v) {
17    if (r < lo || hi < l) return;
18    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, kind, v); return; }   // fully covered: stop, lazily
19    push(node, lo, hi);
20    int mid = lo + (hi - lo) / 2;
21    rangeUpdate(2 * node, lo, mid, l, r, kind, v);
22    rangeUpdate(2 * node + 1, mid + 1, hi, l, r, kind, v);
23    sum[node] = sum[2 * node] + sum[2 * node + 1];
24}
25long query(int node, int lo, int hi, int l, int r) {
26    if (r < lo || hi < l) return 0;
27    if (l <= lo && hi <= r) return sum[node];
28    push(node, lo, hi);
29    int mid = lo + (hi - lo) / 2;
30    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
31}

Live state

0 nodes visited0 push-downs

No condition evaluated on this step

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L1	n=8	A range update would touch O(n) leaves. Lazy propagation stops at the nodes fully covered by the range, fixes their sums at once and leaves a tag saying what the children still owe. The tag is pushed down only when a later operation needs the children.
2	L16	op=+0:5:3	+0:5:3: add 3 to a[0..5].
3	L19	node=1 range=[0, 7]	[0, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
4	L18	node=2 range=[0, 3] sum=22 tag=+3	[0, 3] is fully covered: fix its sum at once (22) and leave the tag +3 for later. The children are not touched.
5	L19	node=3 range=[4, 7]	[4, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
6	L18	node=6 range=[4, 5] sum=17 tag=+3	[4, 5] is fully covered: fix its sum at once (17) and leave the tag +3 for later. The children are not touched.
7	L17	node=7 range=[6, 7]	[6, 7] is outside the range: skip.
8	L23	node=3 sum=32	Recompute [4, 7] = 17 + 15 = 32.
9	L23	node=1 sum=54	Recompute [0, 7] = 22 + 32 = 54.
10	L25	op=?2:6	?2:6: sum of a[2..6]. A query pushes tags down on the way, exactly like an update.
11	L28	node=1	[0, 7] is partly inside: push down, then ask both children.
12	L28	node=2	[0, 3] is partly inside: push down, then ask both children.
13	L12	node=2 tag=+3	Push down: node [0, 3] hands its tag +3 to both children (their sums are corrected and they inherit the tag), then clears it.
14	L26	node=4	[0, 1] is outside: 0.
15	L27	node=5 sum=13	[2, 3] is inside: its sum 13 is already correct even with a pending tag.
16	L28	node=3	[4, 7] is partly inside: push down, then ask both children.
17	L27	node=6 sum=17	[4, 5] is inside: its sum 17 is already correct even with a pending tag.
18	L28	node=7	[6, 7] is partly inside: push down, then ask both children.
19	L27	node=14 sum=7	[6, 6] is inside: its sum 7 is already correct even with a pending tag.
20	L26	node=15	[7, 7] is outside: 0.
21	L30	op=?2:6 return=37	?2:6 = 37.
22	L30	return=37 push-downs=1 nodes visited=14	Done: 14 node visits and 1 push-down for 2 operations. Each operation is O(log n) however long its range is.

29.04.2

Range assignment

Assigning a value to a range, a[l..r] = v, needs a different tag: 'every element below equals v'. A fully covered node sets sum = v × length and remembers the assignment. Unlike an add, a new assignment completely replaces any older tag on the node, because it overwrites whatever was below.

Because 'no assignment pending' cannot be encoded by a value (any number might be assigned), keep a separate boolean flag. Try the preset "Assign, then sum" (=2:5:7 ?3:6): after the assignment the values are 1 2 7 7 7 7 7 8, and the query for positions 3..6 returns 28.

Java

1static long[] sum, setTo;
2static boolean[] pending;                        // pending[node]: an assignment has not reached the children yet
3static int[] a;
4static void init(int[] values) {
5    a = values;
6    sum = new long[4 * a.length];
7    setTo = new long[4 * a.length];
8    pending = new boolean[4 * a.length];
9    build(1, 0, a.length - 1);
10}
11static void build(int node, int lo, int hi) {
12    if (lo == hi) { sum[node] = a[lo]; return; }
13    int mid = lo + (hi - lo) / 2;
14    build(2 * node, lo, mid);
15    build(2 * node + 1, mid + 1, hi);
16    sum[node] = sum[2 * node] + sum[2 * node + 1];
17}
18static void apply(int node, int len, long v) { sum[node] = v * len; setTo[node] = v; pending[node] = true; }
19static void push(int node, int lo, int hi) {
20    if (!pending[node]) return;
21    int mid = lo + (hi - lo) / 2;
22    apply(2 * node, mid - lo + 1, setTo[node]);
23    apply(2 * node + 1, hi - mid, setTo[node]);
24    pending[node] = false;
25}
26static void assign(int node, int lo, int hi, int l, int r, long v) {
27    if (r < lo || hi < l) return;
28    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, v); return; }
29    push(node, lo, hi);
30    int mid = lo + (hi - lo) / 2;
31    assign(2 * node, lo, mid, l, r, v);
32    assign(2 * node + 1, mid + 1, hi, l, r, v);
33    sum[node] = sum[2 * node] + sum[2 * node + 1];
34}
35static long query(int node, int lo, int hi, int l, int r) {
36    if (r < lo || hi < l) return 0;
37    if (l <= lo && hi <= r) return sum[node];
38    push(node, lo, hi);
39    int mid = lo + (hi - lo) / 2;
40    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
41}

Lazy propagation: range add, range assign, range sum

Interactive · edit the input

segment tree: node value = sum of its range; a pending tag is shown after the range (+v add, =v assign) · 15 nodes

[0,7]

[0,3]

[0,1]

[0,0]

[1,1]

[2,3]

[2,2]

[3,3]

[4,7]

[4,5]

[4,4]

[5,5]

[6,7]

[6,6]

[7,7]

Partly inside: push down, recurseFully inside: tag itTag handed down / recomputedOutside

true values a[] (what the tree represents)

Setup

Step 1 / 22

Java

1void apply(int node, int len, int kind, long v) {            // put a tag on node
2    if (kind == SET) { sum[node] = v * len; tagKind[node] = SET; tagVal[node] = v; }
3    else {                                                   // ADD
4        sum[node] += v * len;
5        if (tagKind[node] == NONE) { tagKind[node] = ADD; tagVal[node] = v; }
6        else tagVal[node] += v;                              // ADD after ADD or after SET: just add to the value
7    }
8}
9void push(int node, int lo, int hi) {                        // hand the pending tag to the children
10    if (tagKind[node] == NONE) return;
11    int mid = lo + (hi - lo) / 2;
12    apply(2 * node, mid - lo + 1, tagKind[node], tagVal[node]);
13    apply(2 * node + 1, hi - mid, tagKind[node], tagVal[node]);
14    tagKind[node] = NONE;
15}
16void rangeUpdate(int node, int lo, int hi, int l, int r, int kind, long v) {
17    if (r < lo || hi < l) return;
18    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, kind, v); return; }   // fully covered: stop, lazily
19    push(node, lo, hi);
20    int mid = lo + (hi - lo) / 2;
21    rangeUpdate(2 * node, lo, mid, l, r, kind, v);
22    rangeUpdate(2 * node + 1, mid + 1, hi, l, r, kind, v);
23    sum[node] = sum[2 * node] + sum[2 * node + 1];
24}
25long query(int node, int lo, int hi, int l, int r) {
26    if (r < lo || hi < l) return 0;
27    if (l <= lo && hi <= r) return sum[node];
28    push(node, lo, hi);
29    int mid = lo + (hi - lo) / 2;
30    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
31}

Live state

0 nodes visited0 push-downs

No condition evaluated on this step

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L1	n=8	A range update would touch O(n) leaves. Lazy propagation stops at the nodes fully covered by the range, fixes their sums at once and leaves a tag saying what the children still owe. The tag is pushed down only when a later operation needs the children.
2	L16	op=+0:5:3	+0:5:3: add 3 to a[0..5].
3	L19	node=1 range=[0, 7]	[0, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
4	L18	node=2 range=[0, 3] sum=22 tag=+3	[0, 3] is fully covered: fix its sum at once (22) and leave the tag +3 for later. The children are not touched.
5	L19	node=3 range=[4, 7]	[4, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
6	L18	node=6 range=[4, 5] sum=17 tag=+3	[4, 5] is fully covered: fix its sum at once (17) and leave the tag +3 for later. The children are not touched.
7	L17	node=7 range=[6, 7]	[6, 7] is outside the range: skip.
8	L23	node=3 sum=32	Recompute [4, 7] = 17 + 15 = 32.
9	L23	node=1 sum=54	Recompute [0, 7] = 22 + 32 = 54.
10	L25	op=?2:6	?2:6: sum of a[2..6]. A query pushes tags down on the way, exactly like an update.
11	L28	node=1	[0, 7] is partly inside: push down, then ask both children.
12	L28	node=2	[0, 3] is partly inside: push down, then ask both children.
13	L12	node=2 tag=+3	Push down: node [0, 3] hands its tag +3 to both children (their sums are corrected and they inherit the tag), then clears it.
14	L26	node=4	[0, 1] is outside: 0.
15	L27	node=5 sum=13	[2, 3] is inside: its sum 13 is already correct even with a pending tag.
16	L28	node=3	[4, 7] is partly inside: push down, then ask both children.
17	L27	node=6 sum=17	[4, 5] is inside: its sum 17 is already correct even with a pending tag.
18	L28	node=7	[6, 7] is partly inside: push down, then ask both children.
19	L27	node=14 sum=7	[6, 6] is inside: its sum 7 is already correct even with a pending tag.
20	L26	node=15	[7, 7] is outside: 0.
21	L30	op=?2:6 return=37	?2:6 = 37.
22	L30	return=37 push-downs=1 nodes visited=14	Done: 14 node visits and 1 push-down for 2 operations. Each operation is O(log n) however long its range is.

29.04.3

Lazy tags

A **lazy tag** is a small description of an update that has been applied to a node's own summary but not yet to its children. For a sum tree with add and assign updates the tag is a pair (kind, value): none, add v, or assign v. Applying a tag to a node's sum needs only the node's length: add gives sum + v × length, assign gives v × length.

A tag must satisfy one rule: applying it to the node's summary must give the same answer as applying it to every element and re-summing. The animation shows the pending tag after the range of each node (+3 or =7), so you can see which nodes are owed an update. A node with no tag shows nothing.

Java

1record Tag(int kind, long value) {               // kind: 0 none, 1 add value, 2 assign value
2    static final Tag NONE = new Tag(0, 0);
3    long applyToSum(long sum, int len) {         // the node's new sum
4        switch (kind) {
5            case 1: return sum + value * len;
6            case 2: return value * len;
7            default: return sum;
8        }
9    }
10    long applyToValue(long x) {                  // the same update on a single element
11        switch (kind) {
12            case 1: return x + value;
13            case 2: return value;
14            default: return x;
15        }
16    }
17}

Lazy propagation: range add, range assign, range sum

Interactive · edit the input

segment tree: node value = sum of its range; a pending tag is shown after the range (+v add, =v assign) · 15 nodes

[0,7]

[0,3]

[0,1]

[0,0]

[1,1]

[2,3]

[2,2]

[3,3]

[4,7]

[4,5]

[4,4]

[5,5]

[6,7]

[6,6]

[7,7]

Partly inside: push down, recurseFully inside: tag itTag handed down / recomputedOutside

true values a[] (what the tree represents)

Setup

Step 1 / 22

Java

1void apply(int node, int len, int kind, long v) {            // put a tag on node
2    if (kind == SET) { sum[node] = v * len; tagKind[node] = SET; tagVal[node] = v; }
3    else {                                                   // ADD
4        sum[node] += v * len;
5        if (tagKind[node] == NONE) { tagKind[node] = ADD; tagVal[node] = v; }
6        else tagVal[node] += v;                              // ADD after ADD or after SET: just add to the value
7    }
8}
9void push(int node, int lo, int hi) {                        // hand the pending tag to the children
10    if (tagKind[node] == NONE) return;
11    int mid = lo + (hi - lo) / 2;
12    apply(2 * node, mid - lo + 1, tagKind[node], tagVal[node]);
13    apply(2 * node + 1, hi - mid, tagKind[node], tagVal[node]);
14    tagKind[node] = NONE;
15}
16void rangeUpdate(int node, int lo, int hi, int l, int r, int kind, long v) {
17    if (r < lo || hi < l) return;
18    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, kind, v); return; }   // fully covered: stop, lazily
19    push(node, lo, hi);
20    int mid = lo + (hi - lo) / 2;
21    rangeUpdate(2 * node, lo, mid, l, r, kind, v);
22    rangeUpdate(2 * node + 1, mid + 1, hi, l, r, kind, v);
23    sum[node] = sum[2 * node] + sum[2 * node + 1];
24}
25long query(int node, int lo, int hi, int l, int r) {
26    if (r < lo || hi < l) return 0;
27    if (l <= lo && hi <= r) return sum[node];
28    push(node, lo, hi);
29    int mid = lo + (hi - lo) / 2;
30    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
31}

Live state

0 nodes visited0 push-downs

No condition evaluated on this step

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L1	n=8	A range update would touch O(n) leaves. Lazy propagation stops at the nodes fully covered by the range, fixes their sums at once and leaves a tag saying what the children still owe. The tag is pushed down only when a later operation needs the children.
2	L16	op=+0:5:3	+0:5:3: add 3 to a[0..5].
3	L19	node=1 range=[0, 7]	[0, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
4	L18	node=2 range=[0, 3] sum=22 tag=+3	[0, 3] is fully covered: fix its sum at once (22) and leave the tag +3 for later. The children are not touched.
5	L19	node=3 range=[4, 7]	[4, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
6	L18	node=6 range=[4, 5] sum=17 tag=+3	[4, 5] is fully covered: fix its sum at once (17) and leave the tag +3 for later. The children are not touched.
7	L17	node=7 range=[6, 7]	[6, 7] is outside the range: skip.
8	L23	node=3 sum=32	Recompute [4, 7] = 17 + 15 = 32.
9	L23	node=1 sum=54	Recompute [0, 7] = 22 + 32 = 54.
10	L25	op=?2:6	?2:6: sum of a[2..6]. A query pushes tags down on the way, exactly like an update.
11	L28	node=1	[0, 7] is partly inside: push down, then ask both children.
12	L28	node=2	[0, 3] is partly inside: push down, then ask both children.
13	L12	node=2 tag=+3	Push down: node [0, 3] hands its tag +3 to both children (their sums are corrected and they inherit the tag), then clears it.
14	L26	node=4	[0, 1] is outside: 0.
15	L27	node=5 sum=13	[2, 3] is inside: its sum 13 is already correct even with a pending tag.
16	L28	node=3	[4, 7] is partly inside: push down, then ask both children.
17	L27	node=6 sum=17	[4, 5] is inside: its sum 17 is already correct even with a pending tag.
18	L28	node=7	[6, 7] is partly inside: push down, then ask both children.
19	L27	node=14 sum=7	[6, 6] is inside: its sum 7 is already correct even with a pending tag.
20	L26	node=15	[7, 7] is outside: 0.
21	L30	op=?2:6 return=37	?2:6 = 37.
22	L30	return=37 push-downs=1 nodes visited=14	Done: 14 node visits and 1 push-down for 2 operations. Each operation is O(log n) however long its range is.

29.04.4

Push-down

**Push-down** is the step that gives a node's pending tag to its two children and clears it from the node: each child's sum is corrected and the child's own tag absorbs the new one. It must happen before the recursion looks at the children, in updates and in queries, so that the children are up to date. Skipping it in either place gives wrong answers that only show up after a certain sequence of operations.

A point read is the simplest place to see it: push down along the path from the root to the leaf, and then the leaf is correct. The code below adds pointValue to the range-add tree. After a tag has been pushed, the node has no tag, and the children carry it: nothing is lost, only moved one level down.

Java

1static long pointValue(int node, int lo, int hi, int i) {       // the current value of a[i]
2    if (lo == hi) return sum[node];
3    push(node, lo, hi);                          // make the children correct before descending
4    int mid = lo + (hi - lo) / 2;
5    return i <= mid ? pointValue(2 * node, lo, mid, i) : pointValue(2 * node + 1, mid + 1, hi, i);
6}

Lazy propagation: range add, range assign, range sum

Interactive · edit the input

segment tree: node value = sum of its range; a pending tag is shown after the range (+v add, =v assign) · 15 nodes

[0,7]

[0,3]

[0,1]

[0,0]

[1,1]

[2,3]

[2,2]

[3,3]

[4,7]

[4,5]

[4,4]

[5,5]

[6,7]

[6,6]

[7,7]

Partly inside: push down, recurseFully inside: tag itTag handed down / recomputedOutside

true values a[] (what the tree represents)

Setup

Step 1 / 22

Java

1void apply(int node, int len, int kind, long v) {            // put a tag on node
2    if (kind == SET) { sum[node] = v * len; tagKind[node] = SET; tagVal[node] = v; }
3    else {                                                   // ADD
4        sum[node] += v * len;
5        if (tagKind[node] == NONE) { tagKind[node] = ADD; tagVal[node] = v; }
6        else tagVal[node] += v;                              // ADD after ADD or after SET: just add to the value
7    }
8}
9void push(int node, int lo, int hi) {                        // hand the pending tag to the children
10    if (tagKind[node] == NONE) return;
11    int mid = lo + (hi - lo) / 2;
12    apply(2 * node, mid - lo + 1, tagKind[node], tagVal[node]);
13    apply(2 * node + 1, hi - mid, tagKind[node], tagVal[node]);
14    tagKind[node] = NONE;
15}
16void rangeUpdate(int node, int lo, int hi, int l, int r, int kind, long v) {
17    if (r < lo || hi < l) return;
18    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, kind, v); return; }   // fully covered: stop, lazily
19    push(node, lo, hi);
20    int mid = lo + (hi - lo) / 2;
21    rangeUpdate(2 * node, lo, mid, l, r, kind, v);
22    rangeUpdate(2 * node + 1, mid + 1, hi, l, r, kind, v);
23    sum[node] = sum[2 * node] + sum[2 * node + 1];
24}
25long query(int node, int lo, int hi, int l, int r) {
26    if (r < lo || hi < l) return 0;
27    if (l <= lo && hi <= r) return sum[node];
28    push(node, lo, hi);
29    int mid = lo + (hi - lo) / 2;
30    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
31}

Live state

0 nodes visited0 push-downs

No condition evaluated on this step

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L1	n=8	A range update would touch O(n) leaves. Lazy propagation stops at the nodes fully covered by the range, fixes their sums at once and leaves a tag saying what the children still owe. The tag is pushed down only when a later operation needs the children.
2	L16	op=+0:5:3	+0:5:3: add 3 to a[0..5].
3	L19	node=1 range=[0, 7]	[0, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
4	L18	node=2 range=[0, 3] sum=22 tag=+3	[0, 3] is fully covered: fix its sum at once (22) and leave the tag +3 for later. The children are not touched.
5	L19	node=3 range=[4, 7]	[4, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
6	L18	node=6 range=[4, 5] sum=17 tag=+3	[4, 5] is fully covered: fix its sum at once (17) and leave the tag +3 for later. The children are not touched.
7	L17	node=7 range=[6, 7]	[6, 7] is outside the range: skip.
8	L23	node=3 sum=32	Recompute [4, 7] = 17 + 15 = 32.
9	L23	node=1 sum=54	Recompute [0, 7] = 22 + 32 = 54.
10	L25	op=?2:6	?2:6: sum of a[2..6]. A query pushes tags down on the way, exactly like an update.
11	L28	node=1	[0, 7] is partly inside: push down, then ask both children.
12	L28	node=2	[0, 3] is partly inside: push down, then ask both children.
13	L12	node=2 tag=+3	Push down: node [0, 3] hands its tag +3 to both children (their sums are corrected and they inherit the tag), then clears it.
14	L26	node=4	[0, 1] is outside: 0.
15	L27	node=5 sum=13	[2, 3] is inside: its sum 13 is already correct even with a pending tag.
16	L28	node=3	[4, 7] is partly inside: push down, then ask both children.
17	L27	node=6 sum=17	[4, 5] is inside: its sum 17 is already correct even with a pending tag.
18	L28	node=7	[6, 7] is partly inside: push down, then ask both children.
19	L27	node=14 sum=7	[6, 6] is inside: its sum 7 is already correct even with a pending tag.
20	L26	node=15	[7, 7] is outside: 0.
21	L30	op=?2:6 return=37	?2:6 = 37.
22	L30	return=37 push-downs=1 nodes visited=14	Done: 14 node visits and 1 push-down for 2 operations. Each operation is O(log n) however long its range is.

29.04.5

Tag composition

When a new update reaches a node that already has a tag, the two tags must be merged into one, so that a node never holds a list of tags. The rule for add and assign: a new assign replaces whatever tag was there; a new add after an add just adds the values; a new add after an assign gives an assign of the sum, because the elements are all equal to the assigned value and then grow by the added amount.

The check for a correct composition is: compose(older, newer) applied to any value gives the same result as applying older and then newer. Try the preset "Tag composition: add after assign" (=0:7:2 +0:3:5 ?2:5): the assign puts 2 everywhere, the add makes positions 0..3 equal to 7, and the query for 2..5 returns 7 + 7 + 2 + 2 = 18.

Existing tag	New update	Result
none	add v	add v
add u	add v	add u + v
assign u	add v	assign u + v
any	assign v	assign v

Java

1record Tag(int kind, long value) {               // kind: 0 none, 1 add, 2 assign
2    long applyToValue(long x) {
3        switch (kind) {
4            case 1: return x + value;
5            case 2: return value;
6            default: return x;
7        }
8    }
9}
10static Tag compose(Tag older, Tag newer) {       // equals applying older first, then newer
11    if (newer.kind() == 0) return older;
12    if (newer.kind() == 2 || older.kind() == 0) return newer;      // an assignment overwrites everything before it
13    return new Tag(older.kind(), older.value() + newer.value());   // add after add, or add after assign
14}

Lazy propagation: range add, range assign, range sum

Interactive · edit the input

segment tree: node value = sum of its range; a pending tag is shown after the range (+v add, =v assign) · 15 nodes

[0,7]

[0,3]

[0,1]

[0,0]

[1,1]

[2,3]

[2,2]

[3,3]

[4,7]

[4,5]

[4,4]

[5,5]

[6,7]

[6,6]

[7,7]

Partly inside: push down, recurseFully inside: tag itTag handed down / recomputedOutside

true values a[] (what the tree represents)

Setup

Step 1 / 22

Java

1void apply(int node, int len, int kind, long v) {            // put a tag on node
2    if (kind == SET) { sum[node] = v * len; tagKind[node] = SET; tagVal[node] = v; }
3    else {                                                   // ADD
4        sum[node] += v * len;
5        if (tagKind[node] == NONE) { tagKind[node] = ADD; tagVal[node] = v; }
6        else tagVal[node] += v;                              // ADD after ADD or after SET: just add to the value
7    }
8}
9void push(int node, int lo, int hi) {                        // hand the pending tag to the children
10    if (tagKind[node] == NONE) return;
11    int mid = lo + (hi - lo) / 2;
12    apply(2 * node, mid - lo + 1, tagKind[node], tagVal[node]);
13    apply(2 * node + 1, hi - mid, tagKind[node], tagVal[node]);
14    tagKind[node] = NONE;
15}
16void rangeUpdate(int node, int lo, int hi, int l, int r, int kind, long v) {
17    if (r < lo || hi < l) return;
18    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, kind, v); return; }   // fully covered: stop, lazily
19    push(node, lo, hi);
20    int mid = lo + (hi - lo) / 2;
21    rangeUpdate(2 * node, lo, mid, l, r, kind, v);
22    rangeUpdate(2 * node + 1, mid + 1, hi, l, r, kind, v);
23    sum[node] = sum[2 * node] + sum[2 * node + 1];
24}
25long query(int node, int lo, int hi, int l, int r) {
26    if (r < lo || hi < l) return 0;
27    if (l <= lo && hi <= r) return sum[node];
28    push(node, lo, hi);
29    int mid = lo + (hi - lo) / 2;
30    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
31}

Live state

0 nodes visited0 push-downs

No condition evaluated on this step

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L1	n=8	A range update would touch O(n) leaves. Lazy propagation stops at the nodes fully covered by the range, fixes their sums at once and leaves a tag saying what the children still owe. The tag is pushed down only when a later operation needs the children.
2	L16	op=+0:5:3	+0:5:3: add 3 to a[0..5].
3	L19	node=1 range=[0, 7]	[0, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
4	L18	node=2 range=[0, 3] sum=22 tag=+3	[0, 3] is fully covered: fix its sum at once (22) and leave the tag +3 for later. The children are not touched.
5	L19	node=3 range=[4, 7]	[4, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
6	L18	node=6 range=[4, 5] sum=17 tag=+3	[4, 5] is fully covered: fix its sum at once (17) and leave the tag +3 for later. The children are not touched.
7	L17	node=7 range=[6, 7]	[6, 7] is outside the range: skip.
8	L23	node=3 sum=32	Recompute [4, 7] = 17 + 15 = 32.
9	L23	node=1 sum=54	Recompute [0, 7] = 22 + 32 = 54.
10	L25	op=?2:6	?2:6: sum of a[2..6]. A query pushes tags down on the way, exactly like an update.
11	L28	node=1	[0, 7] is partly inside: push down, then ask both children.
12	L28	node=2	[0, 3] is partly inside: push down, then ask both children.
13	L12	node=2 tag=+3	Push down: node [0, 3] hands its tag +3 to both children (their sums are corrected and they inherit the tag), then clears it.
14	L26	node=4	[0, 1] is outside: 0.
15	L27	node=5 sum=13	[2, 3] is inside: its sum 13 is already correct even with a pending tag.
16	L28	node=3	[4, 7] is partly inside: push down, then ask both children.
17	L27	node=6 sum=17	[4, 5] is inside: its sum 17 is already correct even with a pending tag.
18	L28	node=7	[6, 7] is partly inside: push down, then ask both children.
19	L27	node=14 sum=7	[6, 6] is inside: its sum 7 is already correct even with a pending tag.
20	L26	node=15	[7, 7] is outside: 0.
21	L30	op=?2:6 return=37	?2:6 = 37.
22	L30	return=37 push-downs=1 nodes visited=14	Done: 14 node visits and 1 push-down for 2 operations. Each operation is O(log n) however long its range is.

29.04.6

Mixed updates

With both add and assign updates in the same tree, every step uses the composition rule: apply raises or replaces the node's sum and merges the new tag into the old one, and push hands the single merged tag to both children. The animation implements exactly this; try your own mixed sequences such as =2:5:7 +0:3:1 ?0:7.

The cost stays O(log n) per operation, because composing two tags is O(1) and a push touches only the two children. This pattern generalises: any update that can be applied to a node's summary using only its length, and that composes associatively with other updates of the same family, can be made lazy. Add and multiply (affine updates), assign, and flip (for boolean arrays) are the usual cases.

Java

1static long[] sum, val;
2static int[] kind;                               // pending tag: 0 none, 1 add, 2 assign
3static int[] a;
4static void init(int[] values) {
5    a = values;
6    sum = new long[4 * a.length];
7    val = new long[4 * a.length];
8    kind = new int[4 * a.length];
9    build(1, 0, a.length - 1);
10}
11static void build(int node, int lo, int hi) {
12    if (lo == hi) { sum[node] = a[lo]; return; }
13    int mid = lo + (hi - lo) / 2;
14    build(2 * node, lo, mid);
15    build(2 * node + 1, mid + 1, hi);
16    sum[node] = sum[2 * node] + sum[2 * node + 1];
17}
18static void apply(int node, int len, int k, long v) {
19    if (k == 2) { sum[node] = v * len; kind[node] = 2; val[node] = v; }
20    else {
21        sum[node] += v * len;
22        if (kind[node] == 0) { kind[node] = 1; val[node] = v; }
23        else val[node] += v;                     // add after add, or add after assign
24    }
25}
26static void push(int node, int lo, int hi) {
27    if (kind[node] == 0) return;
28    int mid = lo + (hi - lo) / 2;
29    apply(2 * node, mid - lo + 1, kind[node], val[node]);
30    apply(2 * node + 1, hi - mid, kind[node], val[node]);
31    kind[node] = 0;
32}
33static void update(int node, int lo, int hi, int l, int r, int k, long v) {
34    if (r < lo || hi < l) return;
35    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, k, v); return; }
36    push(node, lo, hi);
37    int mid = lo + (hi - lo) / 2;
38    update(2 * node, lo, mid, l, r, k, v);
39    update(2 * node + 1, mid + 1, hi, l, r, k, v);
40    sum[node] = sum[2 * node] + sum[2 * node + 1];
41}
42static long query(int node, int lo, int hi, int l, int r) {
43    if (r < lo || hi < l) return 0;
44    if (l <= lo && hi <= r) return sum[node];
45    push(node, lo, hi);
46    int mid = lo + (hi - lo) / 2;
47    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
48}

Lazy propagation: range add, range assign, range sum

Interactive · edit the input

segment tree: node value = sum of its range; a pending tag is shown after the range (+v add, =v assign) · 15 nodes

[0,7]

[0,3]

[0,1]

[0,0]

[1,1]

[2,3]

[2,2]

[3,3]

[4,7]

[4,5]

[4,4]

[5,5]

[6,7]

[6,6]

[7,7]

Partly inside: push down, recurseFully inside: tag itTag handed down / recomputedOutside

true values a[] (what the tree represents)

Setup

Step 1 / 22

Java

1void apply(int node, int len, int kind, long v) {            // put a tag on node
2    if (kind == SET) { sum[node] = v * len; tagKind[node] = SET; tagVal[node] = v; }
3    else {                                                   // ADD
4        sum[node] += v * len;
5        if (tagKind[node] == NONE) { tagKind[node] = ADD; tagVal[node] = v; }
6        else tagVal[node] += v;                              // ADD after ADD or after SET: just add to the value
7    }
8}
9void push(int node, int lo, int hi) {                        // hand the pending tag to the children
10    if (tagKind[node] == NONE) return;
11    int mid = lo + (hi - lo) / 2;
12    apply(2 * node, mid - lo + 1, tagKind[node], tagVal[node]);
13    apply(2 * node + 1, hi - mid, tagKind[node], tagVal[node]);
14    tagKind[node] = NONE;
15}
16void rangeUpdate(int node, int lo, int hi, int l, int r, int kind, long v) {
17    if (r < lo || hi < l) return;
18    if (l <= lo && hi <= r) { apply(node, hi - lo + 1, kind, v); return; }   // fully covered: stop, lazily
19    push(node, lo, hi);
20    int mid = lo + (hi - lo) / 2;
21    rangeUpdate(2 * node, lo, mid, l, r, kind, v);
22    rangeUpdate(2 * node + 1, mid + 1, hi, l, r, kind, v);
23    sum[node] = sum[2 * node] + sum[2 * node + 1];
24}
25long query(int node, int lo, int hi, int l, int r) {
26    if (r < lo || hi < l) return 0;
27    if (l <= lo && hi <= r) return sum[node];
28    push(node, lo, hi);
29    int mid = lo + (hi - lo) / 2;
30    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
31}

Live state

0 nodes visited0 push-downs

No condition evaluated on this step

Execution trace (dry run table)Show 22 steps

Step	Line	State	What happens
1	L1	n=8	A range update would touch O(n) leaves. Lazy propagation stops at the nodes fully covered by the range, fixes their sums at once and leaves a tag saying what the children still owe. The tag is pushed down only when a later operation needs the children.
2	L16	op=+0:5:3	+0:5:3: add 3 to a[0..5].
3	L19	node=1 range=[0, 7]	[0, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
4	L18	node=2 range=[0, 3] sum=22 tag=+3	[0, 3] is fully covered: fix its sum at once (22) and leave the tag +3 for later. The children are not touched.
5	L19	node=3 range=[4, 7]	[4, 7] is partly covered: push its tag down first, so the children are correct, then recurse.
6	L18	node=6 range=[4, 5] sum=17 tag=+3	[4, 5] is fully covered: fix its sum at once (17) and leave the tag +3 for later. The children are not touched.
7	L17	node=7 range=[6, 7]	[6, 7] is outside the range: skip.
8	L23	node=3 sum=32	Recompute [4, 7] = 17 + 15 = 32.
9	L23	node=1 sum=54	Recompute [0, 7] = 22 + 32 = 54.
10	L25	op=?2:6	?2:6: sum of a[2..6]. A query pushes tags down on the way, exactly like an update.
11	L28	node=1	[0, 7] is partly inside: push down, then ask both children.
12	L28	node=2	[0, 3] is partly inside: push down, then ask both children.
13	L12	node=2 tag=+3	Push down: node [0, 3] hands its tag +3 to both children (their sums are corrected and they inherit the tag), then clears it.
14	L26	node=4	[0, 1] is outside: 0.
15	L27	node=5 sum=13	[2, 3] is inside: its sum 13 is already correct even with a pending tag.
16	L28	node=3	[4, 7] is partly inside: push down, then ask both children.
17	L27	node=6 sum=17	[4, 5] is inside: its sum 17 is already correct even with a pending tag.
18	L28	node=7	[6, 7] is partly inside: push down, then ask both children.
19	L27	node=14 sum=7	[6, 6] is inside: its sum 7 is already correct even with a pending tag.
20	L26	node=15	[7, 7] is outside: 0.
21	L30	op=?2:6 return=37	?2:6 = 37.
22	L30	return=37 push-downs=1 nodes visited=14	Done: 14 node visits and 1 push-down for 2 operations. Each operation is O(log n) however long its range is.

Practice ladder

Now try it yourself

Easy

Range Sum Query - Mutable

Medium

Count Integers in Intervals
Range Module
My Calendar III

Advanced

Longest Substring of One Repeating Character
Booking Concert Tickets in Groups
Falling Squares

Key takeaways

A lazy tag records an update already applied to a node's summary but not yet to its children.
Push down before looking at the children, in updates and in queries.
Compose tags with an associative rule (a new assign replaces; add after assign becomes assign of the sum) so a node holds one tag.