Tableaux de différences pour les mises à jour de plages
Appliquer rapidement de nombreuses opérations d’ajout sur des plages
Tableaux de différences pour les mises à jour de plages est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 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.
Inversez le problème
Les sommes préfixes permettent de répondre rapidement aux requêtes sur des intervalles. Un tableau de différences inverse cette idée pour appliquer rapidement de nombreuses mises à jour d'intervalles. 🔁
La méthode lente
Ajouter une valeur à chaque élément d'un intervalle, et répéter l'opération de nombreuses fois, coûte O(n) par mise à jour. Pour q mises à jour, ce coût devient énorme.
Enregistrez les changements
Au lieu de modifier chaque case, enregistrez uniquement l'endroit où un changement commence et celui où il se termine. Marquez les extrémités, pas le milieu.
Ce que contient un tableau de différences
Un tableau de différences stocke l'écart entre chaque élément et celui qui le précède. Modifier un seul écart décale toute une portion située plus loin.
L'astuce des deux marques
Pour ajouter v de l à r, ajoutez v à l'indice l et soustrayez v à l'indice r + 1. Deux simples modifications couvrent tout l'intervalle.
diff[l] += v
diff[r + 1] -= vPourquoi soustraire
Le plus en l active le changement ; le moins en r + 1 le désactive. Ensemble, ils limitent la mise à jour à un seul intervalle.
Appliquez toutes les mises à jour à moindre coût
Chaque mise à jour consiste en deux écritures dans le tableau, donc q mises à jour prennent au total O(q). Le travail coûteux est reporté à la fin.
Reconstruisez le tableau final
Après avoir placé toutes les marques, calculez une somme préfixe du tableau de différences. Ce parcours unique reconstruit chaque valeur finale.
for i in range(1, n):
diff[i] += diff[i - 1]Prévoyez une case de protection
Faites un tableau plus long d'une case afin que r + 1 ne dépasse jamais la fin. Cette case de protection supplémentaire évite les erreurs d'indice.
Le coût total
Vous consacrez O(q) à marquer les mises à jour et effectuez un parcours en O(n) pour reconstruire le tableau. Le coût combiné est bien inférieur au O(n fois q) naïf.
Quand cette méthode est avantageuse
Les tableaux de différences sont particulièrement utiles pour compter des réservations, gérer des péages routiers et résoudre tout problème comportant de nombreuses opérations d'ajout sur des intervalles suivies d'une seule lecture finale.
Vérification rapide
Vous ajoutez v à chaque élément de l'indice l à l'indice r.
Récapitulatif
Vous pouvez regrouper les mises à jour d'intervalles avec un tableau de différences : marquez l et r + 1, puis calculez une seule somme préfixe pour reconstruire le tableau. Mises à jour rapides, lecture unique. ✅
Questions Fréquemment Posées
La leçon « Tableaux de différences pour les mises à jour de plages » est-elle gratuite ?
Oui — le texte complet de « Tableaux de différences pour les mises à jour de plages » 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 « Tableaux de différences pour les mises à jour de plages » ?
Appliquer rapidement de nombreuses opérations d’ajout sur des plages 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 4 sur 4.
Combien de temps prend la leçon « Tableaux de différences pour les mises à jour de plages » ?
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
- Construire un tableau de sommes préfixes
- Additionner n’importe quelle plage par soustraction
- Compter les sous-tableaux d’une somme cible
- Tableaux de différences pour les mises à jour de plages