JMU CS280 SP18 WK06

Start

2018-02-13 21:30 CET

JMU CS280 SP18 WK06

End

2018-02-17 05:59 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -186 days 7:28:24

Time elapsed

80:29:00

Time remaining

0:00:00

Problem E
Fenwick Tree

Input

The first line of input contains two integers $N$, $Q$, where $1 \le N \le 5\, 000\, 000$ is the length of the array and $0 \le Q \le 5\, 000\, 000$ is the number of operations. Then follow $Q$ lines giving the operations. There are two types of operations:

  • + $i$ $\delta $” indicates that $a[i]$ is incremented by $\delta $, where $0 \le i < N$ and $-10^9 \le \delta \le 10^9$ (both are integers)

  • ? $i$” is a query for the value of $a[0] + a[1] + \ldots + a[i-1]$, where $0 \le i \le N$ (for $i = 0$ this is interpreted as an empty sum)

Output

For each query in the input, output one line giving the answer to that query.

Sample Input 1 Sample Output 1
10 4
+ 7 23
? 8
+ 3 17
? 8
23
40
Sample Input 2 Sample Output 2
5 4
+ 0 -43
+ 4 1
? 0
? 5
0
-42