BITの一点加算 2 : BITの一点加算 Clojure(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
(BITの一点更新について)
A_1 を A_1 + b に更新することを考えます。先ほど、問題 4 で更新は頂点 1 と根の最短パス上の頂点に対応するもののみでいいことを確認してきました。
更新後をBIT'とします。
BIT'1 = (A_1 + b) = BIT_1 + b
BIT'2 = (A_1 + b) + A_2 = (A_1 + A_2) + b = BIT_2 + b
BIT'4 = (A_1 + b) + A_2 + A_3 + A_4 = (A_1 + A_2 + A_3 + A_4) + b = BIT_4 + b
...
となっており、更新はそれぞれの要素に b を足せばいいことがわかります。他も同様です。
では、問題 4 で求めたインデックスを順番に加算更新を行っていきましょう。
(問題)
長さ n の配列 A が与えられます。問題 3 の方法でBITを構築したあと、与えられた Q 個のクエリを順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
n
A_1 A_2 ... A_n
Q
I_1 b_1
I_2 b_2
...
I_Q b_Q- 1 行目には 1 つの整数 Q が与えられます。
- 1 + i (1 ≦ i ≦ Q) 行目には 2 つの整数 I_i, b_i が与えられます。
- 入力は合計 1 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを Q 行で出力してください。
i 行目には、i 番目のクエリの答えを半角スペース区切りにして出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ n ≦ 500
- 1 ≦ A_i ≦ 10 ^ 9 (1 ≦ i ≦ n)
- 1 ≦ Q ≦ 500
- 1 ≦ I_i ≦ n (1 ≦ i ≦ Q)
- 1 ≦ b_i ≦ 10 ^ 9 (1 ≦ i ≦ Q)
- 入力例1
-
6
1 5 7 9 8 6
5
5 4
1 10
3 9
3 8
4 7
- 出力例1
-
0 1 6 7 22 12 18
0 11 16 7 32 12 18
0 11 16 16 41 12 18
0 11 16 24 49 12 18
0 11 16 24 56 12 18
