Segment tree with lazy propagation: range add and range sum in O(log n), with a counted-operations budget

A bank keeps $n$ accounts in a row and must, many thousands of times, add $x$ to every account in a range $[l, r)$ , or total a range. The figure shows its segment tree for 8 accounts holding $3, 1, 4, 1, 5, 9, 2, 6$ , just after adding 2 to accounts 1 to 6.

Each node shows its sum and its range. The four pieces of [1, 7) are outlined; the tags +2 are adds still owed to the children.

The two requests are:

add(l, r, x): add $x$ to every account $i$ with $l \leq i < r$ (interest, fees, corrections);
total(l, r): the sum of accounts $l$ to $r - 1$ .

A segment tree stores the sum of every range $[l o, h i)$ that halving produces. The root is $[0, n)$ , and a node with more than one account has children $[l o, m i d)$ and $[m i d, h i)$ , where $m i d = ⌊ (l o + h i) / 2 ⌋$ . Any range $[l, r)$ is the union of a few nodes, its pieces: the nodes where a walk from the root stops because they lie wholly inside the range. A total reads its pieces. An add that updated every account would be slow, so it leaves a tag, "+x for everything below", on its pieces instead. This is lazy propagation.

In the figure, add(1, 7, 2) had the pieces $[1, 2)$ , $[2, 4)$ , $[4, 6)$ and $[6, 7)$ , and only the two pieces with children carry the tag.

Background: Range Queries and Segment Trees.

Part A: 6 pieces

The walk from the root stops at $[1, 2)$ , $[2, 4)$ , $[4, 8)$ , $[8, 12)$ , $[12, 14)$ and $[14, 15)$ : 6 pieces. The left end needs one piece at every level below the top, and so does the right end.

Part B: [1, 63), and no range needs more than 10

On each level the pieces of a range number at most 2: one at the left edge and one at the right. Two pieces side by side under the same parent would have been replaced by the parent. The root level contributes nothing to a range other than the whole tree, so a tree with $\log_{2} n + 1$ levels gives at most $2 \log_{2} n - 2$ pieces. That is 10 for 64 accounts. $[1, 63)$ reaches it, one piece on each side at every level from $[1, 2)$ and $[62, 63)$ up to $[16, 32)$ and $[32, 48)$ , and it is the only range that does.

Part C: tags, and pushing them down

Keep this invariant: a node's sum is the true sum of its range, except for tags still held by its ancestors. A node's own tag is an add it has applied to its own sum but not yet to its children.

add(l, r, x). Walk down from the root. At a piece, add $x \cdot (h i - l o)$ to its sum, add $x$ to its tag, and stop. At a node that only overlaps the range, first push its tag down: apply it to both children and clear it. Then recurse into both children, and recompute sum from them on the way back up.
total(l, r). Walk down the same way. Return a piece's sum directly. Push before going below a node.

The walk visits $O (\log n)$ nodes: at most 4 per level, because only the nodes containing $l$ or $r$ are partly covered. Each visit costs a constant number of field reads and writes. The reference solution uses about 13 per level on the grader's hardest sequence, within the budget of 24.

A second solution never pushes. Its tags stay where they land, a node's sum excludes its own tag, and a total adds up the tags on the way down. It is cheaper still, at about 5 per level.

What fails the grader:

Updating every account (the starter): a wide add touches thousands of nodes.
A private list. Answers are right and the tree never changes, so the first check finds the root's sum stale.
Tags without pushing. If a later add only partly overlaps a tagged node, recomputing its sum from its children drops its tag.
Replacing a tag instead of adding to it, so two adds to the same piece count once.
Forgetting to recompute a partly covered node's sum after the recursion.

Going further

Which tags work. Tags must form a monoid acting on the stored values: composing two tags gives a tag, and a tag can update a node's summary from the summary alone. "Multiply by $a$ , then add $b$ " works, since $x \mapsto a x + b$ composes and a sum over $k$ accounts becomes $a S + b k$ .
Fenwick trees handle range add and range sum with two binary indexed trees, using less memory and a smaller constant, but less generality.
Segment tree beats (Ji Ruyi, 2016) handle chmin by storing the maximum, the second maximum and the count of the maximum, and recursing only when a cap would hit more than one value.

References

J. L. Bentley. Solutions to Klee's rectangle problems. Unpublished manuscript, Carnegie Mellon University, 1977.
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications, chapter 10 (more geometric data structures). Springer, 2008.
P. M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience 24(3), 1994.

The Ledger of Ranges

Try your rule first

Part A: 6 pieces

Part B: [1, 63), and no range needs more than 10

Part C: tags, and pushing them down

Going further

References

Pieces of one range