Overview
Un arbre de segments est une structure de donnée qui permet des requêtes de plage et des mises à jour en O(log n).
Analogy
Comme diviser le pays en régions, puis sous-régions — les requêtes sur une province combinent de petites régions connues.
Step-by-step
- Construis l'arbre en divisant récursivement en deux
- Chaque nœud stocke la somme/min/max de sa plage
- Pour les requêtes : combine les nœuds qui couvrent la plage demandée
- Pour les mises à jour : met à jour le nœud feuille et remonte
Visual
[1,3,5,7,9,11]
Racine=36
├─ [1,3,5,7]=16
│ ├─ [1,3]=4
│ └─ [5,7]=12
└─ [9,11]=20
Common mistakes
- Indexation incorrecte (basée sur 0 vs 1)
- Oublier la propagation vers le haut après la mise à jour
Practice questions
- Implémente les requêtes de somme de plage et les mises à jour ponctuelles
- Étends pour les requêtes de minimum de plage
Time
O(log n) par requête/mise à jour