Arbre de segments récursif
On vous donne un tableau de
n éléments. Votre mission est de construire un arbre de segments de façon récursive et de calculer la valeur de chaque nœud de cet arbre. La valeur de chaque nœud correspond à la somme du sous-tableau associé à ce nœud.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000), qui représente le nombre d’éléments dans le tableau.La deuxième ligne contient
n entiers séparés par des espaces (0 ≤ a_i ≤ 10^9), qui représentent les éléments du tableau.Sortie
Affichez l’arbre de segments en faisant apparaître la valeur de tous les nœuds. Chaque niveau de l’arbre de segments doit être imprimé sur une ligne distincte, avec les valeurs séparées par un espace.
Exemples
Entrée | Sortie |
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