Árvore de Segmentos Recursiva
Você tem um array de
n elementos. O seu objetivo é construir uma árvore de segmentos de forma recursiva e calcular o valor de cada nó nessa árvore. O valor de cada nó corresponde à soma do subarray que ele representa.Entrada
A primeira linha da entrada contém um inteiro
n (1 ≤ n ≤ 100 000), que representa a quantidade de elementos no array.A segunda linha contém
n inteiros separados por espaço (), que são os valores do array.Saída
Imprima a árvore de segmentos com todos os valores dos nós. Cada nível da árvore de segmentos deve ser impresso numa linha separada, com cada valor separado por um espaço.
Exemplos
Entrada | Saída |
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