Range Add, Range Sum

Difficulty: 2000 4000 ms 128 MB

lazy-propagation segment-tree

Support A l r v — add v to every element of a_l..r — and Q l r — print the sum of a_l..r.

Input: the first line has N and Q; the second line has the initial array; each of the next Q lines is an operation.

Output: one line per query with the sum.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values|, |v| ≤ 10⁴

Sample Tests

5 4
1 2 3 4 5
Q 1 5
A 2 4 10
Q 3 5
Q 1 1

15
32
1

1 2
0
A 1 1 5
Q 1 1

5

Read the Editorial