FR
RU
EN
ES
ZH
DE
PT
AR
HI
Construction récursive d’un arbre équilibré à partir de sommes préfixes
C++
Hard
recursion
Tâche «Construction récursive d’un arbre équilibré à partir de sommes préfixes»
Étant donné un tableau d’entiers A de taille N. Il faut construire récursivement un arbre binaire où chaque nœud contient la somme préfixe des éléments sur l’intervalle [l, r), ainsi que les indices l et r. La racine correspond à l’intervalle [0, N). Divisez récursivement l’intervalle en deux moitiés (moitié gauche [l, mid), moitié droite [mid, r)) jusqu’à ce que la longueur de l’intervalle devienne 1. Pour chaque nœud, calculez la somme des éléments sur son intervalle. Affichez l’arbre dans l’ordre de parcours en profondeur (pre-order) : pour chaque nœud, affichez l, r et la somme. Utilisez la récursion. N <= 100, les nombres du tableau sont en valeur absolue <= 10^6.
Format d\ entrée
Première ligne : un entier N (1 <= N <= 100). Deuxième ligne : N entiers A[i] (-10^6 <= A[i] <= 10^6).
Format de sortie
Pour chaque nœud dans l’ordre pre-order, affichez trois nombres : l, r, sum. Chaque nœud sur une ligne séparée. Si l’intervalle est vide (l == r), n’affichez rien.
Exemples
Exemple 1
ENTRÉE
4
1 2 3 4
SORTIE
0 4 10
0 2 3
0 1 1
1 2 2
2 4 7
2 3 3
3 4 4
Exemple 2
ENTRÉE
2
-5 5
SORTIE
0 2 0
0 1 -5
1 2 5
main.cpp