http://update.proggen.org/ 2026-04-19T15:58:29+0200 http://update.proggen.org/ http://update.proggen.org/lib/tpl/proggenY/images/favicon.ico text/html 2022-09-22T19:39:27+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=struct:tree:fenwick&rev=1663868367 Binary Indexed Tree (Fenwick Tree) Definition Der nach seinem Erfinder benannte Fenwick Tree dient dazu 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 text/html 2022-09-22T19:39:27+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=struct:tree:start&rev=1663868367 Bäume IN BEARBEITUNG Um dieses Kapitel zu verstehen, sollten Listen beherrscht werden. Listen sind beliebig große Elementsammlungen, die in einer geordneten Reihenfolge vorliegen können. Allerdings haben Listen den Nachteil, dass man sie vollständig durchlaufen muss, um ein Element zu finden. Im Falle einer sortierten Liste, findet man im Idealfall das Element ganz vorne, im schlechtesten Fall findet man das gesuchte Element ganz hinten. Im Schnitt findet man das gesuchte Element Mittig der L…