Fenwick-Baum (Binary Indexed Tree)

Kurz: Ein Fenwick-Baum speichert ein Zahlenfeld so, dass sowohl das Ändern eines Werts als auch Präfixsummen in O(log n) möglich sind.

Genauer: Er ist eine besonders kompakte Alternative zum Segmentbaum, wenn nur Summen (oder ähnliche umkehrbare Operationen) gebraucht werden. Der Baum steckt in einem einfachen Array, und die Indexrechnung nutzt die niedrigste gesetzte Bitstelle.

Im Detail

• Idee: Position i speichert die Summe eines Abschnitts, dessen Länge der größten Zweierpotenz entspricht, die i teilt.
• Abfrage: Präfixsumme bis i: Wert addieren, dann i -= i & -i, bis i 0 ist.
• Änderung: Wert um d ändern: bei i addieren, dann i += i & -i, bis i die Größe überschreitet.
• Bereichssumme: summe(r) - summe(l-1).
• Aufbau: In O(n) möglich, Speicher nur n Zahlen.
• Grenzen: Nicht jede Operation ist umkehrbar. Ein Minimum über Bereiche braucht daher meist den Segmentbaum.

Siehe auch: O-Notation