8637: DSL_2_B : Range Sum Query
[Creator : ]
Description
Write a program which manipulates a sequence A = {$a_1,a_2,...,a_n$} with the following operations:
- add(i,x): add x to $a_i$.
- getSum(s,t): print the sum of $a_s,a_{s+1},…,a_t$.
Note that the initial values of $a_i\ (i=1,2,...,n)$ are 0.
Input
In the first line, $n$ (the number of elements in A) and $q$ (the number of queries) are given.
Then, q queries are given where com represents the type of queries. '0' denotes add($x_i,y_i$) and '1' denotes getSum($x_i,y_i$).
Output
For each getSum operation, print the sum in a line.
Constraints
1≤n≤100,000
1≤q≤100,000
If com$_i$ is 0, then $1≤x_i≤n, 0≤y_i≤1000$.
If com$_i$ is 1, then $1≤x_i≤n, 1≤y_i≤n$.
1≤q≤100,000
If com$_i$ is 0, then $1≤x_i≤n, 0≤y_i≤1000$.
If com$_i$ is 1, then $1≤x_i≤n, 1≤y_i≤n$.
Sample 1 Input
3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2
Sample 1 Output
3
2