You have an array of n integers and must process q operations in order. An operation `1 l r v` adds v to every element from position l to position r, inclusive. An operation `2 l r` asks for the sum of the elements from position l to position r, inclusive. Positions start at 1. Adding to each element one by one is too slow.
The first line has n and q. The second line has the n initial values. Each of the next q lines is either `1 l r v` or `2 l r`.
For every operation of type 2, print the requested sum on its own line, in order.
1 <= n, q <= 200000 |value|, |v| <= 10^9 There is at least one operation of type 2. In the worst case a sum can exceed even a signed 64-bit integer, so use big integers (Python does this automatically).
1000 ms256 MB
5 4 1 2 3 4 5 2 1 5 1 2 4 10 2 1 5 2 3 3
15 45 13
Adding 10 to positions 2..4 gives 1 12 13 14 5: the total is 45 and position 3 holds 13.
