ES
RU
EN
ZH
FR
DE
PT
AR
HI
Construcción recursiva de un árbol balanceado a partir de sumas de prefijos
C++
Hard
recursion
Tarea «Construcción recursiva de un árbol balanceado a partir de sumas de prefijos»
Dado un arreglo de números enteros A de tamaño N. Se requiere construir recursivamente un árbol binario, donde cada nodo contiene la suma de prefijos de los elementos en el segmento [l, r), así como los índices l y r. La raíz corresponde al segmento [0, N). Divida recursivamente el segmento por la mitad (mitad izquierda [l, mid), mitad derecha [mid, r)) hasta que la longitud del segmento sea 1. Para cada nodo, calcule la suma de los elementos en su segmento. Imprima el árbol en orden de recorrido en profundidad (pre-order): para cada nodo, imprima l, r y la suma. Use recursión. N <= 100, números en el arreglo en valor absoluto <= 10^6.
Formato de entrada
Primera línea: un entero N (1 <= N <= 100). Segunda línea: N números enteros A[i] (-10^6 <= A[i] <= 10^6).
Formato de salida
Para cada nodo en orden pre-order, imprima tres números: l, r, sum. Cada nodo en una línea separada. Si el segmento está vacío (l == r), no imprima nada.
Ejemplos
Ejemplo 1
ENTRADA
4
1 2 3 4
SALIDA
0 4 10
0 2 3
0 1 1
1 2 2
2 4 7
2 3 3
3 4 4
Ejemplo 2
ENTRADA
2
-5 5
SALIDA
0 2 0
0 1 -5
1 2 5
main.cpp