Competitions
Дерево Фенвика
Sum on a segment
Array of n integers is given. Find the sum of elements on a segment.
Input
The first line contains two integers n and k - the number of elements in array and number of queries (1 ≤ n ≤ 105
, 0 ≤ k ≤ 105
). Next k lines contain the queries of two types:
- A i x - assign to the i-th element the value of x (1 ≤ i ≤ n, 0 ≤ x ≤
109
); - Q l r - find the sum of numbers in array at positions from l to r (1 ≤ l ≤ r ≤ n).
Initially the array contains zeros.
Output
For each query of type Q l r print the sum of elements on a segment [l; r].
Input example #1
5 9 A 2 2 A 3 1 A 4 2 Q 1 1 Q 2 2 Q 3 3 Q 4 4 Q 5 5 Q 1 5
Output example #1
0 2 1 2 0 5