Décomposition en chaînes lourdes dans les arbres
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 : ...
Publié le 31 mai à 07h30