1466. Every Range Add First, Then Every Range Sum

An array of n zeros is given, indexed from 0. Then u updates arrive, each written l r v: add v to every position from l to r - 1. AFTER all of them, q questions arrive, each written l r and asking for the TOTAL of positions l to r - 1.

Both ranges are HALF-OPEN, so position r is neither changed nor included. Two updates that merely TOUCH, one ending at r and the next beginning at r, therefore change nothing in common, and the same holds for two questions.

Print one line per question.

n = 6 add 2 over [0,3), 3 over [2,5), 1 over [4,6) array becomes 2 2 5 3 4 1 sum [0,6) -> 17 sum [2,4) -> 8 sum [5,6) -> 1

Check the array against the updates before reading on: 2 2 2 0 0 0, then 2 2 5 3 3 0, then 2 2 5 3 4 1. Its total is 17, positions 2 and 3 add to 8, and position 5 alone is 1.

Every update comes before every question. That is the whole design of the problem and it is what the solution should exploit.

## What most people try first

Applying each update by looping over its range and answering each question by looping over its range. Both are O(n) in the worst case, so at u = q = 10^5 and n = 10^5 it is 2 * 10^10 operations.

The second reflex, and the interesting one, is to reach for a Fenwick tree or a segment tree with range update and range query, as in problem 2006. That works and it is not needed. A tree earns its complexity when an update can arrive BETWEEN two questions; here nothing does.

## Two prefix passes, one after the other

``` d = array of n + 1 zeros for each update l r v: d[l] += v; d[r] -= v

value[i] = running total of d through i first pass pre[i + 1] = pre[i] + value[i], pre[0] = 0 second pass

answer to l r = pre[r] - pre[l] ```

O(n + u + q), about 3 * 10^5 steps at the limits, with no structure more complicated than three arrays.

## Why two passes are enough, and what the second one means

The first running total turns the difference array into the values, for the reason given in problem 1464: an update changes the step between neighbours in exactly two places. The second running total turns the values into prefix sums, so any range total is one subtraction.

Doing it the other way round does not work: the prefix sums of a difference array are the values, not the sums of the values. The order of the two passes is what makes the composition mean anything.

## The boundary that breaks a careless implementation

pre[r] - pre[l], with no + 1 or - 1 anywhere, because both ranges are half-open and pre[k] is defined as the total of positions 0 to k - 1. That alignment is the reason to define pre with an extra leading zero rather than starting it at pre[0] = value[0].

The closing write d[r] -= v lands at index n when r equals n, so the difference array needs n + 1 slots.

## Overflow

One position can reach 10^5 updates of 10^5, which is 10^10, already past the 2147483647 a signed 32 bit integer holds. A range total reaches 10^5 such positions, which is 10^15. Both need 64 bits. The individual v values fit in 32 bits comfortably, which is worth noticing rather than widening everything by reflex.

## Related

Problem 2006 answers the same two operations with a Fenwick tree because there they INTERLEAVE, and problem 2002 does range update with point query. This problem exists to make the dividing line explicit: a tree is what you need when an update can arrive between two questions, and two prefix passes are what you need when it cannot. Problem 1464 is the first of the two passes on its own.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ u ≤ 100000` and `1 ≤ q ≤ 100000` - `0 ≤ l < r ≤ n` for every update and every question, and both ranges are half-open - `-100000 ≤ v ≤ 100000` - every update is given before every question