Adds, then sums

Start with a list of n zeros. Apply every add in adds: (l, r, v) adds v to each of a[l:r]. Then return a list with the answer to each query (l, r): the total of a[l:r].

after_adds(7, [(1, 4, 2), (3, 7, 5), (0, 2, 1)],
           [(0, 7), (2, 5), (3, 4), (6, 7)])
# the list becomes [1, 3, 2, 7, 5, 5, 5]
# answers: [28, 14, 7, 5]

Every range is half-open, as in Python slices: (l, r) means positions l up to but not including r, the same values as a[l:r].

Values v can be negative, and a range can be empty (l equal to r).

Limits

• Up to 200,000 positions, 100,000 adds and 100,000 queries. Each add and each query must cost O(1), plus O(n) once.