Fenwick-Baum für Präfixsummen
Führen Sie Punktaktualisierungen und Präfixabfragen in log n aus
Fenwick-Baum für Präfixsummen ist eine kostenlose Coding Interview Prep-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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum Präfix-Arrays scheitern
Ein einfaches Präfixsummen-Array beantwortet Bereichsanfragen sofort, aber nach einem einzigen Update müssen Sie es neu aufbauen. Bei vielen Updates wird das langsam. ⏱️
Der Fenwick-Baum kommt ins Spiel
Der Fenwick-Baum, auch BIT genannt, unterstützt sowohl Punkt-Updates als auch Präfixabfragen in O(log n). Er ist die erste Wahl für dynamische laufende Summen.
Von Grund auf 1-indiziert
Ein Fenwick-Baum verwendet ein 1-indiziertes Array. Den Index 0 nutzen wir als unauffälligen Platzhalter, sodass Ihre eigentlichen Daten bei Position 1 beginnen.
tree = [0] * (n + 1)Der Zauber des niedrigsten gesetzten Bits
Jeder Index deckt einen Block von Werten ab. Die Blockgröße entspricht i & -i, dem niedrigsten gesetzten Bit von i. Dieser eine Trick bildet die Grundlage des gesamten Baums.
lowbit = i & -iEinen einzelnen Punkt aktualisieren
Um an Position i einen Wert zu addieren, springen Sie in jedem Schritt um das lowbit nach vorne und berühren dabei jeden Block, der i enthält.
while i <= n:
tree[i] += delta
i += i & -iEine Präfixsumme abfragen
Um die ersten i Werte zu summieren, gehen Sie rückwärts und subtrahieren in jedem Schritt das lowbit, bis Sie null erreichen.
s = 0
while i > 0:
s += tree[i]
i -= i & -iBeide Schleifen sind logarithmisch
Jede Schleife schaltet pro Iteration ein Bit aus und läuft daher höchstens log n Mal. Deshalb bleiben sowohl Updates als auch Abfragen schnell.
Bereichssumme aus zwei Präfixen
Sie möchten die Summe von l bis r? Berechnen Sie prefix(r) minus prefix(l-1) – genau wie bei einem statischen Präfix-Array, aber jetzt sind auch Updates günstig.
range_sum = query(r) - query(l - 1)Den Baum aufbauen
Beim einfachsten Aufbau rufen Sie für jeden Anfangswert update auf. Das benötigt O(n log n) und ist für die meisten Wettbewerbsaufgaben völlig schnell genug.
for i, v in enumerate(a, 1):
update(i, v)Sehr geringer Speicherbedarf
Ein Fenwick-Baum benötigt nur ein Array der Größe n+1. Dieser kompakte Speicherbedarf ist ein Grund dafür, dass er bei Programmierwettbewerben so beliebt ist. 💾
Wann Sie ein BIT verwenden sollten
Wählen Sie einen Fenwick-Baum, wenn sich Punkt-Updates mit Präfix- oder Bereichssummenabfragen abwechseln. Er ist kurz zu programmieren und schwer zu übertreffen.
Kurztest
Verinnerlichen Sie, wie sich die Schleifen bewegen.
Zusammenfassung: BIT-Grundlagen
Sie haben den Fenwick-Baum kennengelernt: 1-indiziert, angetrieben durch i & -i, mit Punkt-Updates und Präfixabfragen jeweils in O(log n). Als Nächstes verwenden wir ihn zum Inversionszählen. 🎯
Häufig gestellte Fragen
Ist die Lektion „Fenwick-Baum für Präfixsummen“ kostenlos?
Ja — der vollständige Text von „Fenwick-Baum für Präfixsummen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Fenwick-Baum für Präfixsummen“?
Führen Sie Punktaktualisierungen und Präfixabfragen in log n aus Du übst Coding Interview Prep 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep 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 „Fenwick-Baum für Präfixsummen“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-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
- Fenwick-Baum für Präfixsummen
- Inversionen mit einem BIT
- Segmentbaum: Aufbau und Abfragen
- Lazy Propagation für Bereichsaktualisierungen