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.

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.

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.

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})$$$.

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})$$$

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.

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})$$$

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.

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)$$$.

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 )

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).

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})$$$.

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.

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)

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

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.