Range Query - Range Sum Query (RSQ)

時間制限 : 1 sec, メモリ制限 : 131072 KB
英語版はこちら

Range Sum Query

数列 A = {a1, a2,..., an} に対し、次の2つの操作を行うプログラムを作成せよ。

  • add(i, x): aixを加算する。
  • getSum(s, t): as, as+1,...,atの合計値を出力する。

ただし、ai (i = 1, 2,...,n)は、0 で初期化されているものとする。

入力

n q
com1 x1 y1
com2 x2 y2
...
comq xq yq

1行目にAの要素数n, クエリの数qが与えられる。続くq行にクエリが与えられる。comは、クエリの種類を示し、'0'がadd(xi, yi)、'1'がgetSum(xi, yi)を表す。

出力

getSumクエリについて、合計値を1行に出力せよ。

制約

  • 1 ≤ n ≤ 100000
  • 1 ≤ q ≤ 100000
  • comiが0のとき、1 ≤ xi ≤ n, 0 ≤ yi ≤ 1000
  • comiが1のとき、1 ≤ xi ≤ n, 1 ≤ yi ≤ n

入力例 1

3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2

出力例 1

3
2