Arbre de segments : construction et requêtes
Trouver le minimum, le maximum ou la somme d’une plage en log n
Arbre de segments : construction et requêtes est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Au-delà de l'arbre de Fenwick
Un arbre de Fenwick excelle pour les sommes, mais un arbre de segments gère aussi le minimum, le maximum, le PGCD et bien plus encore. C'est l'outil polyvalent des requêtes d'intervalles.
Un arbre sur des intervalles
Chaque nœud possède un intervalle du tableau. La racine couvre tout le tableau ; les enfants le divisent en deux jusqu'à ce que les feuilles contiennent un seul élément.
Stockage dans un tableau
Nous stockons l'arbre dans un tableau plat de taille 2n ou 4n. Le nœud 1 est la racine ; les enfants du nœud i se trouvent aux positions 2i et 2i+1.
seg = [0] * (2 * n)Les feuilles contiennent les données
Dans la version itérative, les valeurs originales se trouvent dans la seconde moitié du tableau, aux indices n à 2n-1.
for i in range(n):
seg[n + i] = a[i]Construire de bas en haut
Chaque nœud interne est le résultat de combine appliqué à ses deux enfants. Remplissez-les de n-1 jusqu'à 1, et l'arbre entier est prêt.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]L'opération combine
La fonction combine définit l'arbre. Utilisez l'addition pour les sommes, min pour les minimums ou max pour les maximums. Remplacez-la pour modifier la requête.
def combine(x, y):
return min(x, y)Mise à jour ponctuelle, puis remontée
Pour modifier une valeur, définissez la feuille, puis remontez jusqu'à la racine en recalculant chaque parent à partir de ses deux enfants.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Interroger un intervalle semi-ouvert
Les requêtes d'intervalles parcourent les deux extrémités et intègrent les nœuds aux limites dans la réponse. L'intervalle est semi-ouvert : il couvre l jusqu'à r exclu.
La boucle de requête itérative
Déplacez l et r l'un vers l'autre. Lorsqu'un indice est une limite impaire, intégrez ce nœud avant d'avancer le pointeur.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Logarithmique aux deux extrémités
La construction coûte O(n), tandis que chaque mise à jour et chaque requête coûte O(log n). C'est cet équilibre qui rend les arbres de segments si polyvalents.
N'oubliez pas l'élément neutre
Commencez votre résultat par l'élément neutre de l'opération : 0 pour la somme, l'infini pour le minimum et moins l'infini pour le maximum. Un mauvais point de départ produit de mauvaises réponses.
res = float('inf')Vérification rapide
Où les données brutes se trouvent-elles dans l'arbre itératif ?
Récapitulatif : des intervalles polyvalents
Vous avez construit un arbre de segments : les feuilles dans la seconde moitié, les parents étant calculés par combine, avec des mises à jour et des requêtes en O(log n) pour la somme, le minimum ou le maximum. 🌳
Apprends Python avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 30
- Leçons
- 120
Questions Fréquemment Posées
La leçon « Arbre de segments : construction et requêtes » est-elle gratuite ?
Oui — le texte complet de « Arbre de segments : construction et requêtes » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Arbre de segments : construction et requêtes » ?
Trouver le minimum, le maximum ou la somme d’une plage en log n Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Arbre de segments : construction et requêtes » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Arbre de Fenwick pour les sommes préfixes
- Inversions avec un BIT
- Arbre de segments : construction et requêtes
- Propagation paresseuse pour les mises à jour de plages