Fenwick-Baum-Indexrechner

Ein Fenwick-Baum, auch binary indexed tree genannt, beantwortet Präfixsummen und Punkt-Updates in logarithmischer Zeit, indem er Teilbereiche speichert, deren Längen Zweierpotenzen sind. Jeder Navigationsschritt hängt von einem Bit-Trick ab: dem niedrigsten gesetzten Bit des aktuellen 1-basierten Index, geschrieben lsb gleich i AND dem Negativen von i im Zweierkomplement. Addiert man dieses lsb, wandert man die Update-Kette; subtrahiert man es, die Präfixabfrage-Kette. Studierende, Wettbewerbsprogrammierer und Bibliotheksautoren brauchen diese Eltern- und Nachfolgeindizes, ohne die Identitäten unter Prüfungsdruck neu abzuleiten. Dieser Fenwick-Baum-Indexrechner akzeptiert einen positiven Index i und optional eine Baumgröße n; er liefert das lsb, den einstufigen Update-Nachfolger und den Abfrage-Elternindex, Binärformen zum Lernen und, wenn n gesetzt ist, den vollständigen Update- und Abfragepfad des klassischen BIT-Codes.

Wie Fenwick-Indizes das niedrigste gesetzte Bit nutzen

In einem 1-basierten binary indexed tree ist die Zelle am Index i für ein zusammenhängendes Segment des zugrundeliegenden Arrays verantwortlich, dessen Länge dem niedrigsten gesetzten Bit von i entspricht. Diese Länge berechnet sich als lsb gleich i AND der Zweierkomplement-Negation von i, oft als i and minus i geschrieben in Sprachen mit modularer Arithmetik auf Festbreiten-Ganzzahlen. Geometrisch isoliert das Umdrehen aller Bits unter dem niedrigstwertigen Einser-Bit diese Zweierpotenz; das bitweise UND mit dem Originalindex ergibt genau diese Potenz.

Die klassische Update-Schleife startet am geänderten Index und ersetzt i wiederholt durch i plus lsb, solange i innerhalb der Baumgröße n bleibt, sodass jeder Schritt zum nächsten Index springt, der das Delta aufnehmen muss. Die klassische Präfixabfrage-Schleife startet am rechten Endpunkt des Präfixes und ersetzt i durch i minus lsb, solange i positiv bleibt, und summiert die verantwortlichen Zellen, die den Bereich von eins bis zum Originalindex überdecken. Zusammen realisieren diese beiden Läufe Bereichssummen über die Inklusion zweier Präfixe.

Ein einzelner Schritt—Update-Nachfolger gleich i plus lsb, Abfrage-Elternindex gleich i minus lsb—reicht, um Off-by-one-Fehler zu debuggen, den Verantwortungsbaum an der Tafel zu zeichnen und zu prüfen, dass eine Implementierung den Lehrbuch-Identitäten entspricht, bevor Sie sie in eine Wettbewerbsvorlage oder eine produktive Analyse-Pipeline integrieren.

Wann die Schritte eines Fenwick-Baums helfen

Trainer im Wettbewerbsprogrammieren und Online-Jurys nutzen einen Fenwick-Baum-Indexrechner, damit Lernende Eltern- und Nachfolgerschritte prüfen können, während sie Update- und Abfrageschleifen von Hand schreiben. Interview-Vorbereitungswerkzeuge brauchen ein deterministisches Orakel, das mit jedem Standard-BIT-Tutorial auf denselben ganzzahligen Eingaben übereinstimmt, einschließlich unangenehmer Indizes, die eins unter einer Zweierpotenz liegen. Fehlgeschlagene Validierung wird nicht berechnet.

Halten Sie Indizes im positiven Zweiunddreißig-Bit-Bereich, fixieren Sie die Pfad-Arrays in Tests, wenn size gesetzt ist, und Sie erhalten reproduzierbare Navigation für Hausaufgaben, Dokumentations-Screenshots und Edge-Worker, ohne eine eigene vollständige Datenstruktur-Sandbox aufzubauen.