Algorithmus

Segmentbäume

Ein Segmentbaum beantwortet Bereichsabfragen wie Summe oder Minimum und ändert Werte in O(log n); der Fenwick-Baum ist die schlanke Variante für Summen.

Ein Segmentbaum ist ein Binärbaum, der für jeden Bereich, der durch wiederholtes Halbieren eines Arrays entsteht, eine Zusammenfassung wie Summe, Minimum oder Maximum speichert. Die Wurzel deckt das ganze Array ab, jedes Blatt ein einzelnes Element, und jeder innere Knoten kombiniert seine beiden Kinder. So lässt sich jede Frage zu einem zusammenhängenden Bereich aus wenigen Knoten beantworten.

Präfixsummen liefern Bereichssummen in O(1), brauchen aber O(n) für eine einzige Änderung; ein unverändertes Array ist schnell beim Ändern, aber langsam bei jeder Abfrage. Ein Segmentbaum erledigt Punktänderungen und Bereichsabfragen beide in O(log n) und passt deshalb überall dort, wo sich Werte ständig ändern und laufend Bereichsfragen eintreffen. Mit Lazy Propagation unterstützt er zusätzlich Bereichsänderungen, etwa das Addieren eines Werts zu einem ganzen Bereich, in O(log n).

Am besten versteht man zuerst, wo Präfixsummen an ihre Grenzen stoßen, zeichnet dann einen kleinen Baum von Hand und verfolgt, welche Knoten eine Abfrage und eine Änderung berühren. Danach schreibt man die kurze iterative Implementierung und einen Fenwick-Baum selbst und übt an klassischen Aufgaben wie Bereichsminimum, Inversionen zählen und Bereichsaddition mit Bereichssumme.