Add, Assign, Range Sum

Difficulty: 1600 5000 ms 128 MB

fenwick

Support three operations on an array: A i v adds v to a_i, S i v assigns a_i = v, and Q l r prints the sum of a_l..r.

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

Output: one line per Q operation.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values| ≤ 10⁶

Sample Tests

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

15
19

1 1
7
Q 1 1

7

Read the Editorial