Recursive Segment Tree
You are given an array of
n elements. Your task is to construct a segment tree recursively and calculate the value of each node in the tree. The value of each node represents the sum of the respective subarray it represents.Input
The first line of the input contains an integer
n (1 ≤ n ≤ 100 000), representing the number of elements in the array.The second line contains
n space-separated integers Output
Print the segment tree with all the values of the nodes. Each level of the segment tree should be printed on a separate line separated by a space.
Examples
Input | Output |
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