For the longest time, I only knew how to use the lazy segtree for Range Add / Range Sum queries. It would take me painstakingly long to solve problems which had lazy propagation in a slightly different form. I then discovered the [Atcoder Lazy Segment Tree template](https://atcoder.github.io/ac-library/production/document_en/lazysegtree.html) ([C++](https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp) / [Python](https://github.com/not522/ac-library-python/blob/master/atcoder/lazysegtree.py)), which would allow you to solve any Lazy Propagation problem by just defining 6 mathematical parameters: `S`, `op`, `mapping`, `composition`, `e` and `id`. This blog is an attempt to explain the math behind Lazy Propagation in an intuitive manner using Socratic dialogue. I would recommend that you guys ponder over the questions before you read the answers.↵
↵
**Prerequisites:** You know how a standard segment tree works. You know how to build it, how to perform point updates, and how to query a range. If you don't, close this tab, learn that, and come back.↵
↵
### Section 1: The Art of Procrastination↵
↵
**Question:** A standard segment tree processes a point update in $O(\log N)$. If a query requires adding a value $v$ to every element in the range `[0, 50000]`, why can't we simply call the point update function in a loop?↵
↵
<spoiler summary="Answer">↵
Doing so results in $O(N \log N)$ time complexity per query, which mathematically guarantees a Time Limit Exceeded (TLE) verdict. To achieve $O(\log N)$ range updates, we must completely defer updating the leaf nodes.↵
</spoiler>↵
↵
**Question:** To achieve $O(\log N)$ updates, we must stop tree traversal early. How do we defer these updates mathematically without losing the data?↵
↵
<spoiler summary="Answer">↵
During the tree traversal, if we encounter a node that is perfectly enveloped by the update query range, we stop. We update that specific node's value, and then we store the operation in a parallel array: the **Lazy Tree**.↵
↵
This tag is a mathematical guarantee: the node itself reflects the update, and it promises to eventually propagate the update to its subtree.↵
</spoiler>↵
↵
**Question:** If a parent node defers updating its children, what is the exact trigger that forces it to finally push the updates down? Define the golden rule of lazy propagation and the exact steps of the `push_down` function.↵
↵
<spoiler summary="Answer">↵
The golden rule of lazy propagation is absolute: **You only push a tag down when forced to traverse into a node's children.** If a new query partially overlaps a node, we must split our traversal to visit its children. Before making that recursive call, we must execute `push_down`:↵
↵
1. The parent applies its pending tag to its immediate left and right children.↵
2. The parent clears its own tag.↵
↵
The parent is now clean, the immediate children hold accurate values, and the procrastination is deferred exactly one layer deeper.↵
</spoiler>↵
↵
---↵
↵
### Section 2: Formalizing the Mathematics↵
↵
**Question:** If a node defers an update and does not visit its children, how does it compute its own correct sum for future queries? If a node represents a segment of $L$ elements and a Range Add $v$ operation arrives, what exact state variables must the node store?↵
↵
<spoiler summary="Answer">↵
It computes it mathematically. If a range update adds $v$ to every element, each of the $L$ elements increases by $v$. The total sum of that segment increases by $v \times L$.↵
↵
This dictates a fundamental truth: a single integer `sum` is insufficient. The node's state must formally be defined as a composite structure $S = (\text{sum}, \text{length})$.↵
</spoiler>↵
↵
**Question:** Formally define the `mapping(f, S)` function. For a Range Add / Range Sum tree, if a tag $v$ arrives at a node with state $S$, what is the exact algebraically updated state?↵
↵
<spoiler summary="Answer">↵
The `mapping(f, S)` function takes an operation $f$ and a state $S$, and returns the strictly updated state in $O(1)$.↵
↵
For Range Add / Range Sum, it evaluates to:↵
`mapping(v, S)` $\to (S.\text{sum} + v \times S.\text{length}, S.\text{length})$↵
</spoiler>↵
↵
**Question:** Queuing multiple pending operations on a single node destroys the $O(1)$ push-down complexity. If a node holding tag $g$ is hit by a new tag $f$, define the `composition(f, g)` function for a Range Add tree to compress them instantly.↵
↵
<spoiler summary="Answer">↵
For range addition, stacking tags is trivial. The operations are just additions, so they compress by adding them together:↵
↵
`composition(f, g)` $\to f + g$↵
↵
When `push_down` is eventually called, the parent passes this single compressed tag down to the children.↵
</spoiler>↵
↵
**Question:** That handles the top-down updates. How do we compute a parent's state from its children during the bottom-up phase of the traversal? Define the `op(left, right)` function for a Range Sum tree.↵
↵
<spoiler summary="Answer">↵
This is the horizontal merge function. When merging two adjacent segments, the lengths add together, and the sums add together.↵
↵
`op(left, right)` $\to (\text{left.sum} + \text{right.sum}, \text{left.length} + \text{right.length})$↵
</spoiler>↵
↵
**Question:** To implement this cleanly, segment trees usually pad out-of-bounds queries or empty nodes with mathematical identities. Define the identity state `e()` and the identity operation `id()` for our Range Add / Range Sum tree.↵
↵
<spoiler summary="Answer">↵
For the state $S$, we need a value that does not alter the result of `op`. This is **`e()`**.↵
`e()` $\to (0, 0)$↵
↵
For the operation $F$, we need a lazy tag that does not alter the state when passed into `mapping`. This is **`id()`**.↵
`id()` $\to 0$↵
↵
With `S`, `op`, `mapping`, `composition`, `e`, and `id` strictly defined, the internal engine of the lazy segment tree is entirely complete. It requires no further hardcoding.↵
</spoiler>↵
↵
---↵
↵
### Section 3: Letting Algebra Dictate the Architecture↵
↵
Once the mechanics of `S`, `op`, `mapping`, `composition`, `e`, and `id` are strictly defined, the tree traversal logic is permanently closed. You never modify it again. Every lazy segment tree problem from this point forward is strictly a mathematical exercise in defining these six objects.↵
↵
We will prove this by escalating the mathematical complexity. ↵
↵
#### Case Study 1: [Range Affine, Range Sum](https://atcoder.jp/contests/practice2/tasks/practice2_k)↵
↵
**The Problem:** You must support two completely different range updates on the same tree: "Add $v$ to all elements in range" and "Multiply all elements in range by $v$".↵
↵
Attempting to track the timeline of different operations via separate variables (e.g., `add_val`, `mult_val`) and boolean flags leads to catastrophic edge cases during `push_down`. Instead of tracking timelines, we must generalize the operation itself.↵
↵
**Question:** How can you represent both "Add $v$" and "Multiply by $v$" as a single, unified mathematical operation?↵
↵
<spoiler summary="Answer">↵
Both addition and multiplication are specific instances of an affine transformation: $f(x) = a \cdot x + b$.↵
↵
* Range Add $v$ becomes $f(x) = 1 \cdot x + v$.↵
* Range Multiply $v$ becomes $f(x) = v \cdot x + 0$.↵
↵
Your operation tag $F$ is no longer a single integer. It is strictly defined as the vector $F = (a, b)$.↵
</spoiler>↵
↵
**Question:** If the state is $S = (\text{sum}, \text{length})$ and the arriving tag is $F = (a, b)$, what is the exact algebraic formula for `mapping(F, S)`?↵
↵
<spoiler summary="Answer">↵
The transformation $a \cdot x + b$ is applied to every individual element in the segment. The original sum is scaled by $a$, and the constant $b$ is added to every single element in the segment (meaning $b$ is added $\text{length}$ times).↵
↵
`mapping(F, S)` strictly returns:↵
`( (F.a * S.sum) + (F.b * S.length), S.length )`↵
</spoiler>↵
↵
**Question:** If a node holds a pending tag $g(x) = a_2 x + b_2$, and a new tag $f(x) = a_1 x + b_1$ arrives, how do we compress them? Define `composition(f, g)` and the identity `id()`.↵
↵
<spoiler summary="Answer">↵
Composition is the strict mathematical evaluation of $f(g(x))$.↵
↵
$f(g(x)) = a_1(a_2 x + b_2) + b_1 = (a_1 a_2)x + (a_1 b_2 + b_1)$↵
↵
`composition(F, G)` simply returns the new vector:↵
`(F.a * G.a, F.a * G.b + F.b)`↵
↵
The identity operation `id()` must leave $x$ entirely unchanged. For $a \cdot x + b = x$, $a$ must be $1$ and $b$ must be $0$.↵
↵
`id()` returns `(1, 0)`.↵
</spoiler>↵
↵
---↵
↵
#### Case Study 2: [Range Add, Range Sum of Squares](https://atcoder.jp/contests/abc455/tasks/abc455_f)↵
↵
**The Problem:** The operation is a simple Range Add $v$, but the query asks for the **Sum of Squares** of all elements in a range.↵
↵
You cannot simply store a `sq_sum` variable and expect it to update correctly. The query dictates the state. We must let the binomial expansion dictate the exact variables our struct requires.↵
↵
**Question:** If a single element $x$ is updated by adding $v$, the new square is $(x + v)^2$. Expand this mathematically across an entire segment of length $L$. Based on the resulting terms, what exact variables must your state $S$ store to compute the new sum of squares in $O(1)$ time?↵
↵
<spoiler summary="Answer">↵
First, expand the binomial for a single element:↵
$(x + v)^2 = x^2 + 2xv + v^2$↵
↵
Now, distribute the summation across an entire segment:↵
$\sum (x + v)^2 = \sum x^2 + 2v \sum x + v^2 \sum 1$↵
↵
Analyze the terms required to compute this new value:↵
↵
* $\sum x^2$ requires the old sum of squares.↵
* $\sum x$ requires the old regular sum.↵
* $\sum 1$ evaluates to the length of the segment.↵
↵
You cannot compute the new sum of squares without the regular sum, and you cannot compute the regular sum without the length. Therefore, your state must explicitly store all three variables:↵
$S = (\text{sq\_sum}, \text{sum}, \text{length})$.↵
</spoiler>↵
↵
**Question:** Given the state $S = (\text{sq\_sum}, \text{sum}, \text{length})$, define the exact `mapping(v, S)` function when a tag $v$ arrives.↵
↵
<spoiler summary="Answer">↵
The `mapping` function executes the expanded algebra simultaneously for all required state variables:↵
↵
1. `S_new.sq_sum = S.sq_sum + 2 * v * S.sum + (v * v) * S.length`↵
2. `S_new.sum = S.sum + v * S.length`↵
3. `S_new.length = S.length`↵
↵
Because the operation is a standard Range Add, `composition(f, g)` remains $f + g$, and `id()` remains $0$. `op(left, right)` simply adds the respective `sq_sum`, `sum`, and `length` fields together.↵
</spoiler>↵
↵
---↵
↵
#### Case Study 3: [Range Flip, Range Inversions](https://atcoder.jp/contests/practice2/tasks/practice2_l)↵
↵
**The Problem:** You are given a binary array consisting only of $0s$ and $1s$. You must support two operations:↵
↵
1. Range Flip: Flip all bits in a range ($0 \to 1$, $1 \to 0$).↵
2. Range Inversions: Count the number of inversions in a range. An inversion is a pair of indices $(i, j)$ such that $i < j$ and $A[i] > A[j]$ (meaning $A[i] = 1$ and $A[j] = 0$).↵
↵
**Question:** To support calculating inversions across ranges, what exact variables must the state $S$ store, and how is the horizontal merge `op(left, right)` defined?↵
↵
<spoiler summary="Answer">↵
Consider the fundamental property of a segment tree: every element in the `left` child comes strictly before every element in the `right` child. ↵
↵
When merging two segments, the total inversions in the combined segment consist of:↵
↵
1. The internal inversions completely within the `left` segment.↵
2. The internal inversions completely within the `right` segment.↵
3. The cross-inversions formed by elements across the boundary.↵
↵
Because every `1` in the `left` segment appears before every `0` in the `right` segment, each `1` on the left forms exactly one inversion with each `0` on the right. The number of cross-inversions is strictly `left.ones * right.zeros`.↵
↵
To compute this in $O(1)$, the state must store the counts of both states:↵
↵
$S = (\text{ones}, \text{zeros}, \text{inversions})$↵
↵
The horizontal merge `op(left, right)` returns:↵
↵
* `ones = left.ones + right.ones`↵
* `zeros = left.zeros + right.zeros`↵
* `inversions = left.inversions + right.inversions + (left.ones * right.zeros)`↵
</spoiler>↵
↵
**Question:** Our lazy tag $F$ is a boolean flag where `true` means "flip the segment". How do we define `mapping(F, S)` to instantly calculate the new number of inversions when a flip arrives?↵
↵
<spoiler summary="Answer">↵
When the segment is flipped, the $0s$ and $1s$ simply swap values.↵
↵
* `S_new.ones = S.zeros`↵
* `S_new.zeros = S.ones`↵
↵
For the inversions, consider the total number of mixed-bit pairs in the segment. The maximum possible number of pairs between differing bits is exactly $S.\text{ones} \times S.\text{zeros}$.↵
↵
Every mixed pair is currently either a $(1, 0)$ inversion or a $(0, 1)$ non-inversion. A flip perfectly reverses their relationship. The inversions become non-inversions, and the non-inversions are upgraded into inversions.↵
↵
Therefore, the `mapping` function computes the new inversions as the complement of the old inversions:↵
↵
* `S_new.inversions = (S.ones * S.zeros) - S.inversions`↵
</spoiler>↵
↵
**Question:** If a node holds a pending flip tag $g$, and a new flip tag $f$ arrives, how do we define `composition(f, g)` and the identity `id()`?↵
↵
<spoiler summary="Answer">↵
Two consecutive flips mathematically cancel each other out. The timeline of operations evaluates to basic parity. ↵
↵
This is perfectly captured by the boolean XOR operation (`^`). ↵
`composition(f, g)` strictly returns `f ^ g`.↵
↵
The identity operation `id()` that leaves the state untouched is trivially `false`.↵
</spoiler>↵
↵
---
↵
**Prerequisites:** You know how a standard segment tree works. You know how to build it, how to perform point updates, and how to query a range. If you don't, close this tab, learn that, and come back.↵
↵
### Section 1: The Art of Procrastination↵
↵
**Question:** A standard segment tree processes a point update in $O(\log N)$. If a query requires adding a value $v$ to every element in the range `[0, 50000]`, why can't we simply call the point update function in a loop?↵
↵
<spoiler summary="Answer">↵
Doing so results in $O(N \log N)$ time complexity per query, which mathematically guarantees a Time Limit Exceeded (TLE) verdict. To achieve $O(\log N)$ range updates, we must completely defer updating the leaf nodes.↵
</spoiler>↵
↵
**Question:** To achieve $O(\log N)$ updates, we must stop tree traversal early. How do we defer these updates mathematically without losing the data?↵
↵
<spoiler summary="Answer">↵
During the tree traversal, if we encounter a node that is perfectly enveloped by the update query range, we stop. We update that specific node's value, and then we store the operation in a parallel array: the **Lazy Tree**.↵
↵
This tag is a mathematical guarantee: the node itself reflects the update, and it promises to eventually propagate the update to its subtree.↵
</spoiler>↵
↵
**Question:** If a parent node defers updating its children, what is the exact trigger that forces it to finally push the updates down? Define the golden rule of lazy propagation and the exact steps of the `push_down` function.↵
↵
<spoiler summary="Answer">↵
The golden rule of lazy propagation is absolute: **You only push a tag down when forced to traverse into a node's children.** If a new query partially overlaps a node, we must split our traversal to visit its children. Before making that recursive call, we must execute `push_down`:↵
↵
1. The parent applies its pending tag to its immediate left and right children.↵
2. The parent clears its own tag.↵
↵
The parent is now clean, the immediate children hold accurate values, and the procrastination is deferred exactly one layer deeper.↵
</spoiler>↵
↵
---↵
↵
### Section 2: Formalizing the Mathematics↵
↵
**Question:** If a node defers an update and does not visit its children, how does it compute its own correct sum for future queries? If a node represents a segment of $L$ elements and a Range Add $v$ operation arrives, what exact state variables must the node store?↵
↵
<spoiler summary="Answer">↵
It computes it mathematically. If a range update adds $v$ to every element, each of the $L$ elements increases by $v$. The total sum of that segment increases by $v \times L$.↵
↵
This dictates a fundamental truth: a single integer `sum` is insufficient. The node's state must formally be defined as a composite structure $S = (\text{sum}, \text{length})$.↵
</spoiler>↵
↵
**Question:** Formally define the `mapping(f, S)` function. For a Range Add / Range Sum tree, if a tag $v$ arrives at a node with state $S$, what is the exact algebraically updated state?↵
↵
<spoiler summary="Answer">↵
The `mapping(f, S)` function takes an operation $f$ and a state $S$, and returns the strictly updated state in $O(1)$.↵
↵
For Range Add / Range Sum, it evaluates to:↵
`mapping(v, S)` $\to (S.\text{sum} + v \times S.\text{length}, S.\text{length})$↵
</spoiler>↵
↵
**Question:** Queuing multiple pending operations on a single node destroys the $O(1)$ push-down complexity. If a node holding tag $g$ is hit by a new tag $f$, define the `composition(f, g)` function for a Range Add tree to compress them instantly.↵
↵
<spoiler summary="Answer">↵
For range addition, stacking tags is trivial. The operations are just additions, so they compress by adding them together:↵
↵
`composition(f, g)` $\to f + g$↵
↵
When `push_down` is eventually called, the parent passes this single compressed tag down to the children.↵
</spoiler>↵
↵
**Question:** That handles the top-down updates. How do we compute a parent's state from its children during the bottom-up phase of the traversal? Define the `op(left, right)` function for a Range Sum tree.↵
↵
<spoiler summary="Answer">↵
This is the horizontal merge function. When merging two adjacent segments, the lengths add together, and the sums add together.↵
↵
`op(left, right)` $\to (\text{left.sum} + \text{right.sum}, \text{left.length} + \text{right.length})$↵
</spoiler>↵
↵
**Question:** To implement this cleanly, segment trees usually pad out-of-bounds queries or empty nodes with mathematical identities. Define the identity state `e()` and the identity operation `id()` for our Range Add / Range Sum tree.↵
↵
<spoiler summary="Answer">↵
For the state $S$, we need a value that does not alter the result of `op`. This is **`e()`**.↵
`e()` $\to (0, 0)$↵
↵
For the operation $F$, we need a lazy tag that does not alter the state when passed into `mapping`. This is **`id()`**.↵
`id()` $\to 0$↵
↵
With `S`, `op`, `mapping`, `composition`, `e`, and `id` strictly defined, the internal engine of the lazy segment tree is entirely complete. It requires no further hardcoding.↵
</spoiler>↵
↵
---↵
↵
### Section 3: Letting Algebra Dictate the Architecture↵
↵
Once the mechanics of `S`, `op`, `mapping`, `composition`, `e`, and `id` are strictly defined, the tree traversal logic is permanently closed. You never modify it again. Every lazy segment tree problem from this point forward is strictly a mathematical exercise in defining these six objects.↵
↵
We will prove this by escalating the mathematical complexity. ↵
↵
#### Case Study 1: [Range Affine, Range Sum](https://atcoder.jp/contests/practice2/tasks/practice2_k)↵
↵
**The Problem:** You must support two completely different range updates on the same tree: "Add $v$ to all elements in range" and "Multiply all elements in range by $v$".↵
↵
Attempting to track the timeline of different operations via separate variables (e.g., `add_val`, `mult_val`) and boolean flags leads to catastrophic edge cases during `push_down`. Instead of tracking timelines, we must generalize the operation itself.↵
↵
**Question:** How can you represent both "Add $v$" and "Multiply by $v$" as a single, unified mathematical operation?↵
↵
<spoiler summary="Answer">↵
Both addition and multiplication are specific instances of an affine transformation: $f(x) = a \cdot x + b$.↵
↵
* Range Add $v$ becomes $f(x) = 1 \cdot x + v$.↵
* Range Multiply $v$ becomes $f(x) = v \cdot x + 0$.↵
↵
Your operation tag $F$ is no longer a single integer. It is strictly defined as the vector $F = (a, b)$.↵
</spoiler>↵
↵
**Question:** If the state is $S = (\text{sum}, \text{length})$ and the arriving tag is $F = (a, b)$, what is the exact algebraic formula for `mapping(F, S)`?↵
↵
<spoiler summary="Answer">↵
The transformation $a \cdot x + b$ is applied to every individual element in the segment. The original sum is scaled by $a$, and the constant $b$ is added to every single element in the segment (meaning $b$ is added $\text{length}$ times).↵
↵
`mapping(F, S)` strictly returns:↵
`( (F.a * S.sum) + (F.b * S.length), S.length )`↵
</spoiler>↵
↵
**Question:** If a node holds a pending tag $g(x) = a_2 x + b_2$, and a new tag $f(x) = a_1 x + b_1$ arrives, how do we compress them? Define `composition(f, g)` and the identity `id()`.↵
↵
<spoiler summary="Answer">↵
Composition is the strict mathematical evaluation of $f(g(x))$.↵
↵
$f(g(x)) = a_1(a_2 x + b_2) + b_1 = (a_1 a_2)x + (a_1 b_2 + b_1)$↵
↵
`composition(F, G)` simply returns the new vector:↵
`(F.a * G.a, F.a * G.b + F.b)`↵
↵
The identity operation `id()` must leave $x$ entirely unchanged. For $a \cdot x + b = x$, $a$ must be $1$ and $b$ must be $0$.↵
↵
`id()` returns `(1, 0)`.↵
</spoiler>↵
↵
---↵
↵
#### Case Study 2: [Range Add, Range Sum of Squares](https://atcoder.jp/contests/abc455/tasks/abc455_f)↵
↵
**The Problem:** The operation is a simple Range Add $v$, but the query asks for the **Sum of Squares** of all elements in a range.↵
↵
You cannot simply store a `sq_sum` variable and expect it to update correctly. The query dictates the state. We must let the binomial expansion dictate the exact variables our struct requires.↵
↵
**Question:** If a single element $x$ is updated by adding $v$, the new square is $(x + v)^2$. Expand this mathematically across an entire segment of length $L$. Based on the resulting terms, what exact variables must your state $S$ store to compute the new sum of squares in $O(1)$ time?↵
↵
<spoiler summary="Answer">↵
First, expand the binomial for a single element:↵
$(x + v)^2 = x^2 + 2xv + v^2$↵
↵
Now, distribute the summation across an entire segment:↵
$\sum (x + v)^2 = \sum x^2 + 2v \sum x + v^2 \sum 1$↵
↵
Analyze the terms required to compute this new value:↵
↵
* $\sum x^2$ requires the old sum of squares.↵
* $\sum x$ requires the old regular sum.↵
* $\sum 1$ evaluates to the length of the segment.↵
↵
You cannot compute the new sum of squares without the regular sum, and you cannot compute the regular sum without the length. Therefore, your state must explicitly store all three variables:↵
$S = (\text{sq\_sum}, \text{sum}, \text{length})$.↵
</spoiler>↵
↵
**Question:** Given the state $S = (\text{sq\_sum}, \text{sum}, \text{length})$, define the exact `mapping(v, S)` function when a tag $v$ arrives.↵
↵
<spoiler summary="Answer">↵
The `mapping` function executes the expanded algebra simultaneously for all required state variables:↵
↵
1. `S_new.sq_sum = S.sq_sum + 2 * v * S.sum + (v * v) * S.length`↵
2. `S_new.sum = S.sum + v * S.length`↵
3. `S_new.length = S.length`↵
↵
Because the operation is a standard Range Add, `composition(f, g)` remains $f + g$, and `id()` remains $0$. `op(left, right)` simply adds the respective `sq_sum`, `sum`, and `length` fields together.↵
</spoiler>↵
↵
---↵
↵
#### Case Study 3: [Range Flip, Range Inversions](https://atcoder.jp/contests/practice2/tasks/practice2_l)↵
↵
**The Problem:** You are given a binary array consisting only of $0s$ and $1s$. You must support two operations:↵
↵
1. Range Flip: Flip all bits in a range ($0 \to 1$, $1 \to 0$).↵
2. Range Inversions: Count the number of inversions in a range. An inversion is a pair of indices $(i, j)$ such that $i < j$ and $A[i] > A[j]$ (meaning $A[i] = 1$ and $A[j] = 0$).↵
↵
**Question:** To support calculating inversions across ranges, what exact variables must the state $S$ store, and how is the horizontal merge `op(left, right)` defined?↵
↵
<spoiler summary="Answer">↵
Consider the fundamental property of a segment tree: every element in the `left` child comes strictly before every element in the `right` child. ↵
↵
When merging two segments, the total inversions in the combined segment consist of:↵
↵
1. The internal inversions completely within the `left` segment.↵
2. The internal inversions completely within the `right` segment.↵
3. The cross-inversions formed by elements across the boundary.↵
↵
Because every `1` in the `left` segment appears before every `0` in the `right` segment, each `1` on the left forms exactly one inversion with each `0` on the right. The number of cross-inversions is strictly `left.ones * right.zeros`.↵
↵
To compute this in $O(1)$, the state must store the counts of both states:↵
↵
$S = (\text{ones}, \text{zeros}, \text{inversions})$↵
↵
The horizontal merge `op(left, right)` returns:↵
↵
* `ones = left.ones + right.ones`↵
* `zeros = left.zeros + right.zeros`↵
* `inversions = left.inversions + right.inversions + (left.ones * right.zeros)`↵
</spoiler>↵
↵
**Question:** Our lazy tag $F$ is a boolean flag where `true` means "flip the segment". How do we define `mapping(F, S)` to instantly calculate the new number of inversions when a flip arrives?↵
↵
<spoiler summary="Answer">↵
When the segment is flipped, the $0s$ and $1s$ simply swap values.↵
↵
* `S_new.ones = S.zeros`↵
* `S_new.zeros = S.ones`↵
↵
For the inversions, consider the total number of mixed-bit pairs in the segment. The maximum possible number of pairs between differing bits is exactly $S.\text{ones} \times S.\text{zeros}$.↵
↵
Every mixed pair is currently either a $(1, 0)$ inversion or a $(0, 1)$ non-inversion. A flip perfectly reverses their relationship. The inversions become non-inversions, and the non-inversions are upgraded into inversions.↵
↵
Therefore, the `mapping` function computes the new inversions as the complement of the old inversions:↵
↵
* `S_new.inversions = (S.ones * S.zeros) - S.inversions`↵
</spoiler>↵
↵
**Question:** If a node holds a pending flip tag $g$, and a new flip tag $f$ arrives, how do we define `composition(f, g)` and the identity `id()`?↵
↵
<spoiler summary="Answer">↵
Two consecutive flips mathematically cancel each other out. The timeline of operations evaluates to basic parity. ↵
↵
This is perfectly captured by the boolean XOR operation (`^`). ↵
`composition(f, g)` strictly returns `f ^ g`.↵
↵
The identity operation `id()` that leaves the state untouched is trivially `false`.↵
</spoiler>↵
↵
---
