Ein Präfixsummen-Array erstellen
Berechnen Sie laufende Summen einmal vorab
Ein Präfixsummen-Array erstellen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Das Problem wiederholter Summen
Stellen Sie sich vor, Sie müssten Hunderte von Bereichssummen für ein Array beantworten. Jede Summe von Grund auf neu zu berechnen ist langsam. Eine Präfixsumme schafft Abhilfe. 🚀
Was eine Präfixsumme ist
Ein Präfixsummenarray speichert an jedem Index die Gesamtsumme aller Elemente bis zu dieser Position. Ein einziger Vorberechnungslauf verwandelt langsame Summen in sofortige Antworten.
Ein kleines Beispiel
Für [3, 1, 4] lauten die laufenden Summen zunächst 3, dann 4 und schließlich 8. Diese wachsende Liste von Summen ist genau Ihre Präfixsumme.
Die zentrale Rekurrenz
Jeder Eintrag ist die vorherige Summe plus das aktuelle Element. Diese einzeilige Rekurrenz bildet den Kern der gesamten Technik.
prefix[i] = prefix[i - 1] + a[i]Im Code aufbauen
Durchlaufen Sie das Array einmal und führen Sie dabei eine laufende Summe mit. Bei jedem Schritt hängen Sie die neue Summe an, sodass der Aufbau des Arrays ein einziger linearer Durchlauf ist.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Warum eine führende Null hilft
Wenn Sie prefix mit einer führenden Null beginnen, enthält prefix[i] die Summe der ersten i Elemente. Das vereinfacht die Bereichsberechnung später.
Indexkonvention
Mit der Null am Anfang entspricht prefix[k] der Summe a[0] + ... + a[k-1]. Wenn Sie diese Konvention einhalten, vermeiden Sie schmerzhafte Off-by-one-Fehler.
Aufbaukosten
Beim Aufbau des Präfixarrays wird jedes Element genau einmal verarbeitet, daher kostet er O(n) Zeit. Diese Kosten fallen einmal an, danach können Sie das Ergebnis beliebig oft wiederverwenden.
Einmal vorberechnen, oft abfragen
Der große Vorteil ist der Kompromiss: Sie investieren am Anfang einen linearen Durchlauf, sodass jede spätere Summenabfrage zu einem schnellen Zugriff statt zu einer Schleife wird.
Eine Python-Abkürzung
Die Standardbibliothek kann die Summen für Sie aufbauen. itertools.accumulate erzeugt die laufenden Summen mit einem einzigen übersichtlichen Aufruf.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Den Speicher im Blick behalten
Das Präfixarray ist genauso lang wie die Eingabe plus eins. Denken Sie bei sehr großen Eingaben daran, dass sich dadurch Ihr Speicherbedarf verdoppelt.
Kurzer Check
Sie erstellen ein Präfixarray. Was enthält Index 0 normalerweise?
Zusammenfassung
Sie haben gelernt, in einem O(n)-Durchlauf ein Präfixsummenarray mit einer führenden Null für eine einfache Indexierung aufzubauen. Einmal vorberechnen, dann wiederverwenden. ✅
Häufig gestellte Fragen
Ist die Lektion „Ein Präfixsummen-Array erstellen“ kostenlos?
Ja — der vollständige Text von „Ein Präfixsummen-Array erstellen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Ein Präfixsummen-Array erstellen“?
Berechnen Sie laufende Summen einmal vorab Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Ein Präfixsummen-Array erstellen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Ein Präfixsummen-Array erstellen
- Jeden Bereich durch Subtraktion summieren
- Teilarrays mit einer Zielsummme zählen
- Differenz-Arrays für Bereichsaktualisierungen