Dima and large array#2940
Dima received a special array of length as a present from his mother. Dima can choose any index (1 \leq i \leq n) and an integer (-1000 \leq d \leq 1000), and add to the element at that index. Dima enjoys playing with the array, and from time to time, his mother asks him questions. Specifically, she asks for the sum of the elements in the array within a given range of indices from to (inclusive). However, as she is very busy, she can ask no more than such questions. Dima easily handles these requests, but can you?
The first line contains two integers and (1 \leq n \leq 10^6, 1 \leq q \leq 5 \cdot 10^5) --- the number of elements in the array and the total number of operations and queries.
The second line contains integers: a_1, a_2, \ldots, a_n (-1000 \leq a_i \leq 1000) --- the initial state of the array.
Each of the following lines describes either an operation or a query. The first character of the line can be either '+' or '?'.
If the line begins with '+', it is an add operation, followed by two integers and (1 \leq i \leq n, -1000 \leq d \leq 1000), meaning is added to a_i.
If the line begins with '?', it is a query, and is followed by two integers and (1 \leq f, t \leq n), asking for the sum of the elements with indices from to (inclusive).
For each query, print the sum of the elements in the specified range on a separate line.
مثال 1