L'Atelier Monstre

L'arbre de segments (Segment Tree) est une structure de données avancée, basée sur le principe de diviser pour régner. Il s'agit d'une structure arborescente binaire principalement conçue pour résoudre des problèmes d'intervalle ou de plage. Cette structure permet de maintenir des variables qui satisfont la propriété d'associativité (comme le m ...

Principe fondamental Transformer un arbre en une séquence linéaire où n'importe quel chemin correspond à au plus O(log n) segments consécutifs. Définitions essentielles Fils lourd : enfant dont la sous-arbre contient le plus de nœuds Fils léger : tout enfant n'étant pas fils lourd Arête lourde : reliant un nœud à son fils lourd Arête légère : ...