Árbol de Segmentos Recursivo
Se te proporciona un arreglo de
n elementos. Tu tarea consiste en construir un árbol de segmentos de manera recursiva y calcular el valor de cada nodo en dicho árbol. El valor de cada nodo corresponde a la suma del subarreglo que representa.Entrada
La primera línea de la entrada contiene un número entero
n (1 ≤ n ≤ 100 000), que representa el número de elementos en el arreglo.La segunda línea contiene
n enteros separados por espacio (), que representan los elementos del arreglo.Salida
Imprime el árbol de segmentos con todos los valores de los nodos. Cada nivel del árbol debe aparecer en una línea separada, con los valores separados por espacios.
Ejemplos
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