0649 - 区間和(セグ木、BIT練習)

時間制限 4 秒 / メモリ制限 256 MB / 得点 5 / Writer tinumu / x 37 / 統計 /


TLE
4sec
MLE
256MB
得点
5

問題

整数 N が与えられ、配列 A が与えられるので、次の Q 個のクエリを処理せよ。

1 ≦ iQであるsi,ai,biには次のような意味を持つ。 siが0の時、Aaiの値に biだけ加算をする。 siが1の時、Aaiから、Abiまでの総和を求める。

最初、 A の配列の中身の値は全て0である。

制約

  • 1 ≦ N ≦ 106
  • 1 ≦ Q ≦ 106
  • siが0の時、
    • 1 ≦ ai ≦ N
    • 1 ≦ bi ≦ 109
  • siが1の時、
    • 1 ≦ aibi ≦ N
  • siは0か1である。

Aの中身の値や、総和がint型の最大値231 - 1を超える可能性があることに注意して下さい。

入出力形式

N Q
s1 a1 b1
s2 a2 b2
    …
    …
sQ aQ bQ

出力はsi = 1のクエリの際に一行に総和を出力するものとする。

よって、最終的に出力されるのは、複数行からなる。

入出力例

入力例

4 6
0 1 2
0 2 5
1 1 4
0 3 8
0 4 2
1 1 4

出力例

7
17