Dynamic Range Sum

Difficulty: 1700 4000 ms 128 MB

segment-tree

Support two operations on an array: U i v assigns a_i = v, and Q l r prints the sum of a_l..r. Operations arrive interleaved, so precomputed prefixes go stale — a tree structure is required.

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 Q operation with the requested sum.

Constraints:

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

Sample Tests

5 4
1 2 3 4 5
Q 2 4
U 3 10
Q 2 4
Q 1 5

9
16
22

1 2
7
U 1 -5
Q 1 1

-5

Read the Editorial