Startseite▸Algorithmen & KI▸Segmentbaum — Bereichssummen- & Bereichsminimum-Abfragen

🌲 Segmentbaum — Bereichssummen- & Bereichsminimum-Abfragen

Baue einen Segmentbaum über einem Array in O(n) und beantworte Bereichssummen- oder Bereichsminimum-Abfragen sowie Punktänderungen in O(log n). Klicke einen Bereich an, um zu sehen, welche O(log n) Knoten kombiniert werden.

Algorithmen & KI2DFortgeschritten60 FPS

Über Segmentbaum — Bereichssummen- & Bereichsminimum-Abfragen

Ein Segmentbaum ist ein binärer Baum, der über den Indizes eines Arrays aufgebaut ist, wobei jeder Knoten einen zusammenhängenden Bereich repräsentiert und einen aggregierten Wert speichert — eine Summe, ein Minimum, ein Maximum oder eine andere assoziative Kombination — dieses Bereichs, berechnet aus seinen beiden Kindern. Der Aufbau benötigt O(n) Zeit und etwa 2n bis 4n Knoten für ein Array mit n Elementen. Eine Bereichsabfrage über [L, R] steigt rekursiv im Baum ab, verwendet sofort das vorberechnete Aggregat eines Knotens, wenn dessen Bereich vollständig innerhalb von [L, R] liegt, überspringt Bereiche, die vollständig außerhalb liegen, und rekursiert nur bei Teilüberlappungen in die Kinder; dies berührt höchstens O(log n) Knoten, weil sich die Abfrage pro Ebene in eine begrenzte Anzahl kanonischer Teilbereiche zerlegt. Eine Punktänderung muss nur die O(log n) Vorfahren auf dem Pfad vom geänderten Blatt zur Wurzel neu berechnen. Im Vergleich zu Präfixsummen, die Bereichssummen in O(1) beantworten, aber O(n) benötigen, um ein Element zu aktualisieren, und Bereichsminima überhaupt nicht unterstützen können, tauscht ein Segmentbaum einen kleinen konstanten Abfrage-Mehraufwand gegen O(log n) Änderungen und Unterstützung für jeden assoziativen Operator ein.

Häufig gestellte Fragen

Warum berührt eine Segmentbaum-Abfrage nur O(log n) Knoten?

Jeder Abfragebereich [L, R] lässt sich in höchstens O(log n) „kanonische" Knotenbereiche zerlegen — auf jeder Rekursionsebene kann die Abfragegrenze höchstens zwei Knoten in Teilüberlappungen aufteilen, während alles, was strikt zwischen diesen Grenzen liegt, entweder vollständig eingeschlossen oder vollständig ausgeschlossen ist. Summiert man diesen begrenzten Aufwand über die O(log n) Ebenen des Baums, ergibt sich die gesamte O(log n) Abfragekosten.

Warum einen Segmentbaum statt Präfixsummen für Bereichsabfragen verwenden?

Präfixsummen beantworten eine Bereichssummen-Abfrage in O(1), benötigen aber O(n) Aufwand, um ein einzelnes Array-Element zu aktualisieren, da sich jede nachfolgende Präfixsumme verschiebt. Präfixsummen können außerdem überhaupt keine Bereichsminimum-Abfragen beantworten, da Subtraktion kein Analogon für das Minimum hat. Ein Segmentbaum unterstützt sowohl Punktänderungen als auch Bereichsabfragen — für jeden assoziativen Operator — in O(log n).

Wie breitet sich eine Punktänderung durch den Baum aus?

Das Aktualisieren des Arrays an einem Index ändert genau ein Blatt. Die Änderung wandert dann entlang des eindeutigen Pfads von diesem Blatt zur Wurzel nach oben und berechnet dabei das Aggregat jedes Vorfahren als Kombination der aktuellen Werte seiner beiden Kinder neu. Da der Baum die Höhe O(log n) hat, werden insgesamt O(log n) Knoten berührt.

Wie viel Speicher verbraucht ein Segmentbaum?

Ein rekursiver oder array-basierter Segmentbaum über n Elementen verwendet je nach Implementierung typischerweise zwischen 2n und 4n Knoten (ein gängiges array-basiertes Layout reserviert 4n Plätze, um Größen zu handhaben, die keine Zweierpotenz sind, ohne sorgfältige Indizierung). Das ist ein konstanter Mehraufwand im Vergleich zum O(n) großen Eingabe-Array, ein geringer Preis für O(log n) Abfragen und Änderungen.

⚙ Unter der Haube

DatenstrukturBereichsabfrageBaumTeile und herrsche

2D · HTML5 Canvas 2D · Ziel: 60 FPS · läuft vollständig clientseitig, keine Installation nötig