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

問題

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

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

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

制約

• 1 ≦ N ≦ 10⁶
• 1 ≦ Q ≦ 10⁶
• s_iが0の時、
  • 1 ≦ a_i ≦ N
  • 1 ≦ b_i ≦ 10⁹
• s_iが1の時、
  • 1 ≦ a_i ≦ b_i ≦ N
• s_iは0か1である。

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

入出力形式

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

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

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

入出力例

入力例

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

出力例

7
17