Range Add, Range Sum

A spreadsheet column holds a list of numbers. Users often add the same amount to a whole block of rows (a bonus for a range of employee ids, a price change for a range of products) and ask for the total of a block. Build a RangeSums class:

• RangeSums(nums) starts from the list of whole numbers nums.
• add(left, right, value) adds value to every number in the slice [left:right] (left included, right not). If left == right nothing changes.
• total(left, right) returns the sum of the current numbers in the slice [left:right], or 0 when left == right.

Both methods should take about log n steps, where n = len(nums).

Examples

rs = RangeSums([1, 2, 3, 4, 5])
rs.total(0, 5)        # returns 15
rs.add(1, 4, 10)      # the numbers are now [1, 12, 13, 14, 5]
rs.total(0, 2)        # returns 13
rs.total(2, 5)        # returns 32
rs.add(0, 5, -1)      # [0, 11, 12, 13, 4]
rs.total(4, 5)        # returns 4

Constraints

• 1 <= len(nums) <= 100,000 and 0 <= left <= right <= len(nums)
• Numbers and added values are whole numbers between -10^9 and 10^9
• Up to 30,000 calls. Adding to each number of a block one by one, or adding up a block number by number, is too slow when blocks are tens of thousands of numbers long.