Segment Tree (Arbre de segments)
TODO: explication plus détaillée du segtree
Un segment tree (arbre de segments) est une structure de données basée sur un arbre binaire qui représente un tableau ou une liste d’éléments. Chaque nœud de l’arbre représente un segment ou une sous-partie du tableau original.
Dans un segment tree, le nœud racine représente l’intégralité du tableau, tandis que les feuilles représentent les éléments individuels du tableau. Les nœuds internes correspondent à des segments obtenus en divisant le tableau en sous-tableaux plus petits.
En général, si un nœud représente le sous-tableau [l, r], son enfant gauche représentera [l, (l+r)/2] et son enfant droit représentera [(l+r)/2 + 1, r]. Cette division récursive se poursuit jusqu’à ce que chaque feuille corresponde à un seul élément du tableau initial.
La valeur stockée dans chaque nœud dépend du problème ou de la requête à traiter. On utilise fréquemment les segment trees pour calculer rapidement des valeurs agrégées comme la somme, le minimum, le maximum ou d’autres opérations sur un sous-tableau donné. La valeur d’un nœud est ainsi calculée à partir de celles de ses nœuds enfants.
Les segment trees sont particulièrement utiles pour des problèmes impliquant des requêtes ou des mises à jour sur des plages (range) d’un tableau. Grâce à la construction d’un segment tree, on peut effectuer ces opérations en O(log N), où N est la taille du tableau initial.
Dans l’ensemble, le segment tree est une structure de données puissante pour la gestion d’opérations sur des plages dans un tableau et permet des requêtes et mises à jour efficaces. Il est utilisé dans de nombreux algorithmes et problèmes, notamment les requêtes sur des intervalles, les mises à jour de plages, et plus encore.
Défi : Calcul itératif des nœuds d’un Segment Tree
Vous disposez d’un tableau de
n éléments. Votre tâche consiste à construire un segment tree de façon itérative et à calculer la valeur de chaque nœud de l’arbre. La valeur de chaque nœud représente la somme du sous-tableau qui lui est associé.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 du tableau.La deuxième ligne contient
n entiers séparés par un espace (), qui correspondent aux éléments du tableau.Sortie
Imprimez le segment tree avec les valeurs de tous ses nœuds. Chaque niveau de l’arbre doit être imprimé sur une ligne distincte, les valeurs étant séparées par un espace.
Exemples
Input | Output |
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