再帰的セグメント木 (Recursive Segment Tree)
n 個の要素からなる配列が与えられています。あなたの任務は再帰的にセグメント木を構築し、各ノードの値を計算することです。ここで、ノードの値は対応する部分配列の合計を表します。
入力
最初の行には、配列に含まれる要素数を示す整数 n (1 ≤ n ≤ 100000) が与えられます。
2 行目には、スペース区切りで n 個の整数 () が与えられます。これらが配列の要素です。
出力
構築したセグメント木のすべてのノードの値を出力してください。各レベルごとに、同じ段階のノードをスペース区切りで 1 行にまとめて表示します。
例
入力 | 出力 |
4
1 2 3 4 | 10
3 7
1 2 3 4 |
8
3 7 9 6 2 1 5 4 | 37
25 12
10 15 3 9
3 7 9 6 2 1 5 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 10 MB