区間和クエリ 2
n 個の要素からなる配列と q 個のクエリが与えられています。クエリには、以下の 2 種類があります。
- 指定された区間の要素の合計を求める
- 指定された位置の配列要素を更新する
これらのクエリを効率的に処理することが求められます。
入力
最初の行には、配列の要素数を表す整数 n と、クエリの数を表す整数 q (1 ≤ n, q ≤ 100000) が与えられます。
次の行には、空白区切りで n 個の整数
a_1, a_2, ..., a_n (−10^9 ≤ ai ≤ 10^9) が与えられます。これは配列の初期状態を表します。続く q 行には、それぞれクエリが 1 行ずつ与えられます:
- 区間和クエリの場合: 行の先頭が
1で、続けて li と ri (1 ≤ li ≤ ri ≤ n) が与えられます。指定された範囲[l_i, r_i]の要素の合計を求めます。
- 配列の更新クエリの場合: 行の先頭が
2で、続けて pi と xi (1 ≤ pi ≤ n, −10^9 ≤ xi ≤ 10^9) が与えられます。これは配列の pi 番目の要素を新しい値 xi に更新する操作です。
出力
区間和クエリごとに、指定された範囲の要素の合計を 1 行につき 1 つずつ出力してください。
例
入力例 | 出力例 |
5 3
1 2 3 4 5
1 1 3
1 2 4
1 1 5 | 6
9
15 |
5 3
1 2 3 4 5
1 1 3
2 1 5
1 1 5 | 6
19 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB