Construire un tableau de sommes préfixes
Précalculer une fois les totaux cumulés
Construire un tableau de sommes préfixes est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème des sommes répétées
Imaginez que vous deviez répondre à des centaines de questions sur des sommes d’intervalles dans un même tableau. Calculer chaque somme depuis le début est lent. Une somme préfixe résout ce problème. 🚀
Qu’est-ce qu’une somme préfixe
Un tableau de sommes préfixes stocke, à chaque indice, le total de tous les éléments jusqu’à cet indice. Un seul parcours de précalcul transforme les sommes lentes en réponses instantanées.
Un petit exemple
Pour [3, 1, 4], les totaux cumulés sont 3, puis 4, puis 8. Cette liste croissante de totaux constitue exactement votre somme préfixe.
La récurrence essentielle
Chaque entrée est égale au total précédent plus l’élément actuel. Cette récurrence d’une seule ligne est au cœur de toute la technique.
prefix[i] = prefix[i - 1] + a[i]La construire en code
Parcourez le tableau une fois en conservant un total cumulé. À chaque étape, ajoutez la nouvelle somme : la construction du tableau est donc un seul parcours linéaire.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Pourquoi un zéro initial aide
Commencer prefix par un zéro initial signifie que prefix[i] contient la somme des i premiers éléments. Cela simplifie les calculs d’intervalles par la suite.
Convention d’indexation
Avec le zéro initial, prefix[k] est égal à a[0] + ... + a[k-1]. Respecter cette convention évite les erreurs pénibles de décalage d’un indice.
Coût de la construction
La construction du tableau de sommes préfixes touche chaque élément exactement une fois : elle coûte donc O(n) en temps. Vous payez ce coût une fois, puis vous réutilisez le tableau indéfiniment.
Précalculer une fois, interroger souvent
Le grand avantage est ce compromis : effectuer un parcours linéaire initial afin que chaque requête de somme ultérieure devienne une recherche rapide plutôt qu’une boucle.
Une abréviation idiomatique en Python
La bibliothèque standard peut construire les totaux à votre place. itertools.accumulate produit les sommes cumulées en un seul appel clair.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Surveiller la mémoire
Le tableau de sommes préfixes a la même longueur que votre entrée, plus un élément. Pour les entrées volumineuses, n’oubliez pas qu’il double votre empreinte mémoire.
Vérification rapide
Vous construisez un tableau de sommes préfixes. Que contient généralement l’indice 0 ?
Récapitulatif
Vous avez appris à construire un tableau de sommes préfixes en un seul parcours en O(n), avec un zéro initial pour simplifier l’indexation. Précalculez une fois, puis réutilisez. ✅
Questions Fréquemment Posées
La leçon « Construire un tableau de sommes préfixes » est-elle gratuite ?
Oui — le texte complet de « Construire un tableau de sommes préfixes » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Construire un tableau de sommes préfixes » ?
Précalculer une fois les totaux cumulés Tu pratiques Coding Interview Prep 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep 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 1 sur 4.
Combien de temps prend la leçon « Construire un tableau de sommes préfixes » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep 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