Add to a range, sum a range

Write a segment tree with lazy propagation (lesson 5). There are n values, all starting at 0. add(l, r, v) adds v to every value of a[l:r], and total(l, r) returns the sum of a[l:r]. Adds and totals come mixed, in any order.

t = RangeTree(8)
t.add(1, 7, 3)
t.total(0, 8)     # 18
t.total(5, 7)     # 6
t.add(0, 4, 1)
t.total(3, 5)     # 7

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

v can be negative, and a range can be empty (then add does nothing and total is 0).

Limits

• Up to 200,000 values and 4,000 operations over wide ranges. Each operation should cost O(log n).