PT
RU
EN
ES
ZH
FR
DE
AR
HI
Construção recursiva de uma árvore balanceada a partir de somas de prefixos
C++
Hard
recursion
Tarefa «Construção recursiva de uma árvore balanceada a partir de somas de prefixos»
Dado um array de inteiros A de tamanho N. É necessário construir recursivamente uma árvore binária, onde cada nó contém a soma de prefixo dos elementos no intervalo [l, r), bem como os índices l e r. A raiz corresponde ao intervalo [0, N). Divida recursivamente o intervalo pela metade (metade esquerda [l, mid), metade direita [mid, r)), até que o comprimento do intervalo seja 1. Para cada nó, calcule a soma dos elementos em seu intervalo. Imprima a árvore em ordem de travessia em profundidade (pre-order): para cada nó, imprima l, r e a soma. Use recursão. N <= 100, números no array em módulo <= 10^6.
Formato de Entrada
Primeira linha: inteiro N (1 <= N <= 100). Segunda linha: N inteiros A[i] (-10^6 <= A[i] <= 10^6).
Formato de Saída
Para cada nó na ordem pre-order, imprima três números: l, r, sum. Cada nó em uma linha separada. Se o intervalo estiver vazio (l == r), não imprima nada.
Exemplos
Exemplo 1
ENTRADA
4
1 2 3 4
SAÍDA
0 4 10
0 2 3
0 1 1
1 2 2
2 4 7
2 3 3
3 4 4
Exemplo 2
ENTRADA
2
-5 5
SAÍDA
0 2 0
0 1 -5
1 2 5
main.cpp