2006. Add Across a Range, Total Across a Range

An array of n integers is given, numbered from 1. Then q operations arrive:

add l r v add v to every position from l to r inclusive sum l r print the total of positions l through r inclusive

Print one line for each sum.

1 2 3 4 5 sum 1 5 -> 15 add 2 4 10 the array becomes 1 12 13 14 5 sum 1 5 -> 45 sum 3 3 -> 13

## What most people try first

Both previous structures, and neither is enough on its own.

The Fenwick tree over a difference array, from problem 2002, does range add and point read. Ask it for a range SUM and it has nothing to offer: it stores differences, and summing them over a range is not a quantity it can produce in O(log n).

The segment tree from 2004 does range query and point update. Extending its update to a range by calling the point version r - l + 1 times is O((r - l + 1) log n), which is worse than the plain loop it replaced.

What is needed is a range update that does not descend to the leaves at all.

## Stop at the nodes that are fully covered

A range l .. r decomposes into O(log n) nodes that lie entirely inside it. For each, the effect of adding v to every element under it is known immediately: the node's total rises by v * (size of the node). There is no need to visit anything below.

So update the node, and leave a note on it saying "everything beneath me still owes v". That note is the LAZY tag:

add(node, l, r, v): if node range is disjoint from [l, r]: return if node range is inside [l, r]: total[node] += v * size(node) lazy[node] += v return push(node) # settle the debt before recursing recurse into both children total[node] = total[left] + total[right]

## The push is not optional

Before a query or an update descends into a child, any tag sitting on the parent must be handed down, because the child's stored total does not yet include it:

push(node): for each child: total[child] += lazy[node] * size(child) lazy[child] += lazy[node] lazy[node] = 0

Skip it and the tree returns stale numbers for any range that cuts across a tagged node. On 1 1 1 1 with add 1 2 2, add 3 4 3 then sum 2 3, the answer is 7 and a version without the push reports 2. That input is a declared test, and so is one where the whole-range total stays correct while a sub-range is wrong, which is what makes this bug survive casual checking.

## Why the totals stay consistent

The invariant is that total[node] is the true sum of its range INCLUDING every tag at or above it, while lazy[node] records what has not yet been pushed to its children. A fully covered node updates both at once. A partially covered one pushes first, so its children are true, then recomputes itself from them.

## Overflow

2 * 10^5 values of 10^9 already total 2 * 10^14, and 2 * 10^5 range adds of 10^9 can raise a single position by another 2 * 10^14. Both the node totals and the tags need 64 bits. Note that 2 * 10^9, which two such adds produce at one position, still FITS in a signed 32 bit integer, since the limit is 2147483647; it is the accumulation that does not.

## Cost

O(log n) per operation, roughly 4 nodes per level, so about 70 node visits at n = 200000 and 1.4 * 10^7 for 2 * 10^5 operations.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ each starting value ≤ 10^9` - `1 ≤ l ≤ r ≤ n` - `-10^9 ≤ v ≤ 10^9`