セグメント木

TODO: より詳細なセグメント木の説明を追加予定

セグメント木は、与えられた配列（あるいはリスト）の要素を表すための二分木をベースにしたデータ構造です。木の各ノードは、元の配列の区間（サブ配列）を表しています。

セグメント木では、根ノードが配列全体を表し、葉ノードが配列の各個要素を表します。内部ノードは配列をさらに小さな区間に分割して得られるサブ配列を表します。

一般的に、あるノードが [l, r] という区間を表しているとき、その左の子ノードは [l, (l+r)/2] を表し、右の子ノードは [(l+r)/2 + 1, r] を表すように再帰的に分割していきます。再帰的な分割を続け、最終的に葉ノードが配列の1要素だけをカバーするようになります。

各ノードに格納する値は、解きたい問題や与えられたクエリ内容によって変わります。たとえば、区間内の合計、最小値、最大値などを高速に求めたい場合にセグメント木を活用することが多いです。ノードの値は、それぞれの子ノードの値をもとに算出されます。

セグメント木は、配列に対する区間クエリや更新操作を効率的に処理できるのが特徴で、クエリや更新を行うたびに O(log N) の計算量で対応できます（N は元の配列の要素数）。

このようにセグメント木は、区間ベースの演算が必要となるさまざまなアルゴリズムや問題で役立ち、区間クエリや更新が繰り返し行われる場面で効率を大幅に向上させる重要なデータ構造です。

n 個の要素からなる配列が与えられます。これをもとにセグメント木を反復的に構築し、各ノードの値を計算してください。ノードの値は、そのノードが表すサブ配列の要素合計とします。

1 行目に配列の要素数を表す整数 n (1 ≤ n ≤ 100 000) が与えられます。

2 行目には長さ n の空白区切り整数 (0 ≤ a_i ≤ 10^9) が与えられます。

構築したセグメント木のすべてのノードの値を出力してください。セグメント木の各レベルを 1 行ずつ出力し、同じレベルにあるノードの値は空白で区切って並べます。