====== Binary Indexed Tree (Fenwick Tree) ======
===== Definition =====
Der nach seinem Erfinder benannte Fenwick Tree dient dazu [[algo:cumulativesum|kumulative Summen]] zu verwalten und effizient zu bearbeiten. Ändert man einen Wert in einer Reihe, muss die kumulative Summe für alle darauffolgenden Elemente aktualisiert werden. Diese Operation wird durch den Binary Indexed Tree beschleunigt und die Ordnung von O(n) auf **O(log n)** verbessert.

===== Implementierung ====
==== Erstellung eines Binary Indexed Trees ====
==== Werte abfragen ====
==== Werte aktualisieren ====


===== Anwendungsbeispiel ====


===== Siehe auch =====
  * [[algo:prefix-sum:start|Präfixsumme]]
  * [[algo:recursion|Rekursionen]]