Additionner n’importe quelle plage par soustraction
Répondre pour range[l..r] en temps constant
Additionner n’importe quelle plage par soustraction est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 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.
Le véritable avantage
La construction du tableau de sommes préfixes n’était que la préparation. Voici maintenant la magie : répondre à toute somme d’intervalle avec une seule soustraction. ⚡
L’idée essentielle
Une somme d’intervalle est simplement un grand total moins un total plus petit. Soustraire deux valeurs de sommes préfixes annule proprement tout ce qui se trouve en dehors de votre intervalle.
La formule
Pour additionner les éléments de l à r, prenez prefix[r + 1] moins prefix[l]. Cette unique formule fonctionne pour tout intervalle.
range_sum = prefix[r + 1] - prefix[l]Pourquoi cela fonctionne
prefix[r + 1] contient tout jusqu'à r, tandis que prefix[l] contient tout ce qui précède l. La différence laisse exactement la portion centrale.
Un exemple détaillé
Pour [3, 1, 4], le préfixe est [0, 3, 4, 8]. Pour additionner les indices 1 à 2, calculez 8 moins 3, ce qui donne 5. Cela correspond bien à 1 plus 4.
Requêtes en temps constant
Chaque requête consiste simplement en une soustraction, donc elle s'exécute en O(1). Mille requêtes coûtent autant par requête qu'une seule.
Attention au décalage d'une unité
L'erreur la plus courante concerne l'indice de la borne supérieure. Avec un zéro initial, utilisez toujours prefix[r + 1], et non prefix[r]. Vérifiez cette limite.
Inclusif ou exclusif
Décidez dès le début si r est inclus. Cette formule considère l'intervalle comme inclusif de l et de r, ce qu'attendent la plupart des problèmes de concours.
Placez-le dans une fonction
Une petite fonction auxiliaire rend votre logique plus lisible et regroupe vos indices au même endroit. Appuyez-vous sur cette fonction auxiliaire plutôt que d'intégrer les calculs directement.
def query(l, r):
return prefix[r + 1] - prefix[l]Traitez tout le tableau
Pour additionner le tableau entier, utilisez l égal à 0 et r égal à n moins 1. La formule donne prefix[n], le total général.
Quand cette méthode est particulièrement utile
Chaque fois qu'un problème pose de nombreuses questions de somme sur un intervalle d'un tableau fixe, les sommes préfixes transforment une boucle en O(n) par requête en réponses instantanées.
Vérification rapide
Vous voulez calculer la somme des indices de l à r inclus.
Récapitulatif
Vous pouvez maintenant calculer toute somme sur un intervalle en O(1) avec prefix[r + 1] moins prefix[l]. Faites attention au décalage dû au zéro initial et vous éviterez les bogues. ✅
Questions Fréquemment Posées
La leçon « Additionner n’importe quelle plage par soustraction » est-elle gratuite ?
Oui — le texte complet de « Additionner n’importe quelle plage par soustraction » 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 « Additionner n’importe quelle plage par soustraction » ?
Répondre pour range[l..r] en temps constant 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 2 sur 4.
Combien de temps prend la leçon « Additionner n’importe quelle plage par soustraction » ?
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