data-structures
Segmentbaum
Suche…
Einführung in den Segmentbaum
Angenommen, wir haben ein Array:
+-------+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+-------+-----+-----+-----+-----+-----+-----+
| Value | -1 | 3 | 4 | 0 | 2 | 1 |
+-------+-----+-----+-----+-----+-----+-----+
Wir möchten eine Abfrage für dieses Array durchführen. Zum Beispiel:
- Was ist das Minimum von Index 2 bis Index 4 ? -> 0
- Was ist das Maximum von Index 0 bis Index 3 ? -> 4
- Was ist die Summe von Index 1 bis Index 5 ? -> 10
Wie finden wir es heraus?
Rohe Gewalt:
Wir könnten das Array vom Startindex zum Endindex bringen und unsere Abfrage beantworten. Bei diesem Ansatz benötigt jede Abfrage O(n)
Zeit, wobei n die Differenz zwischen dem Startindex und dem Endindex ist. Was aber, wenn es Millionen von Zahlen und Millionen von Anfragen gibt? Für m Abfragen würde es O(mn)
Zeit dauern. Für 10⁵ Werte in unserem Array müssen wir also, wenn wir 10⁵ Abfragen durchführen, im schlimmsten Fall 10¹⁰ Elemente durchlaufen.
Dynamische Programmierung:
Wir können eine 6X6-Matrix erstellen, um die Werte für verschiedene Bereiche zu speichern. Für die Bereichsminimumabfrage (RMQ) würde unser Array folgendermaßen aussehen:
0 1 2 3 4 5
+-----+-----+-----+-----+-----+-----+-----+
| | -1 | 3 | 4 | 0 | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
+-----+-----+-----+-----+-----+-----+-----+
1 | 3 | | 3 | 3 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
2 | 4 | | | 4 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
3 | 0 | | | | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
4 | 2 | | | | | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
5 | 1 | | | | | | 1 |
+-----+-----+-----+-----+-----+-----+-----+
Sobald wir diese Matrix erstellt haben, reicht es aus, alle RMQs zu beantworten. Hier würde Matrix [i] [j] den Minimalwert von Index- i bis Index- j speichern. Zum Beispiel: Das Minimum von Index- 2 bis Index- 4 ist Matrix [2] [4] = 0 . Diese Matrix beantwortet die Abfrage in O(1)
-Zeit, aber es braucht O (n²) - Zeit, um diese Matrix zu erstellen, und O(n²)
Raum, um sie zu speichern. Wenn also n eine wirklich große Zahl ist, lässt sich dies nicht gut skalieren.
Segmentbaum:
Ein Segmentbaum ist eine Baumdatenstruktur zum Speichern von Intervallen oder Segmenten. Es ermöglicht die Abfrage, welche der gespeicherten Segmente einen bestimmten Punkt enthalten. Es dauert O(n)
Zeit, um einen Segmentbaum aufzubauen, es erfordert O(n)
Platz, um ihn zu verwalten, und er beantwortet eine Anfrage in O(logn)
Zeit.
Der Segmentbaum ist ein binärer Baum und die Elemente des angegebenen Arrays sind die Blätter dieses Baums. Wir erstellen den Segmentbaum, indem wir das Array in zwei Hälften teilen, bis wir ein einzelnes Element erreichen. Unsere Abteilung würde uns also Folgendes bieten:
Wenn wir nun die Nichtblattknoten durch den minimalen Wert ihrer Blätter ersetzen, erhalten wir:
Das ist also unser Segmentbaum. Wir können feststellen, dass der Wurzelknoten den Minimalwert des gesamten Arrays (Bereich [0,5]) enthält, sein linkes Kind den Minimalwert unseres linken Arrays (Bereich [0,2]) und das rechte Kind das Minimum Wert unseres rechten Arrays (Bereich [3,5]) und so weiter. Die Blattknoten enthalten einen Mindestwert für jeden einzelnen Punkt. Wir bekommen:
Lassen Sie uns nun eine Bereichsabfrage für diesen Baum durchführen. Um eine Bereichsabfrage durchzuführen, müssen wir drei Bedingungen überprüfen:
- Teilüberlappung: Wir prüfen beide Blätter.
- Gesamtüberlappung: Wir geben den im Knoten gespeicherten Wert zurück.
- Keine Überlappung: Wir geben einen sehr großen Wert oder unendlich zurück.
Nehmen wir an, wir wollen den Bereich [2,4] überprüfen, das heißt, wir wollen das Minimum von Index 2 bis 4 ermitteln . Wir starten vom Stamm aus und prüfen, ob der Bereich in unseren Knoten von unserem Abfragebereich überlappt wird oder nicht. Hier,
- [2,4] überschneidet sich nicht vollständig [0,5] . Also prüfen wir beide Richtungen.
- Im linken Teilbaum überlappt [ 2,4] teilweise [0,2] . Wir prüfen beide Richtungen.
- Im linken Teilbaum überschneidet sich [2,4] nicht mit [0,1] , sodass dies nicht zu unserer Antwort beitragen wird. Wir kehren ins Unendliche zurück .
- Im rechten Teilbaum überschneidet sich [ 2,4] vollständig [2,2] . Wir kehren zurück 4 .
Das Minimum dieser beiden Rückgabewerte (4, unendlich) beträgt 4 . Wir bekommen 4 von diesem Teil.
- Im rechten Teilbaum überschneidet sich [2,4] teilweise. Also prüfen wir beide Richtungen.
- Im linken Teilbaum überlappt [ 2,4] [3,4] vollständig. Wir geben 0 zurück .
- Beim rechten Teilbaum überlappt [ 2,4] nicht [5,5] . Wir kehren ins Unendliche zurück .
Das Minimum dieser beiden zurückgegebenen Werte (0, unendlich) ist 0 . Wir bekommen 0 von diesem Teil.
- Im linken Teilbaum überlappt [ 2,4] teilweise [0,2] . Wir prüfen beide Richtungen.
- Das Minimum der zurückgegebenen Werte (4,0) ist 0 . Dies ist unser gewünschtes Minimum im Bereich [2,4] .
Jetzt können wir überprüfen, dass unabhängig von unserer Abfrage maximal 4 Schritte erforderlich sind, um den gewünschten Wert aus diesem Segmentbaum zu finden.
Benutzen:
- Bereichsminimale Abfrage
- Niedrigster gemeinsamer Vorfahr
- Lazy Propagation
- Dynamische Teilbaumsumme
- Vernachlässigung & min
- Doppelfelder
- Suche nach dem kleinsten k-ten Element
- Anzahl der ungeordneten Paare ermitteln
Implementierung des Segmentbaums mit Array
Nehmen wir an, wir haben ein Array: Item = {-1, 0, 3, 6}
. Wir möchten ein SegmentTree- Array erstellen , um den Mindestwert in einem bestimmten Bereich herauszufinden. Unser Segmentbaum wird folgendermaßen aussehen:
Die Zahlen unter den Knoten zeigen die Indizes der einzelnen Werte, die wir in unserem SegmentTree- Array speichern. Wir können sehen, dass wir zum Speichern von 4 Elementen ein Array der Größe 7 benötigten. Dieser Wert wird bestimmt durch:
Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size
Wenn wir also ein Array der Länge 5 hätten, wäre die Größe unseres SegmentTree- Arrays: ( 8 * 2 ) - 1 = 15 . Um nun die Position des linken und rechten untergeordneten Elements eines Knotens zu bestimmen, wenn sich ein Knoten im Index i befindet , dann ist dessen Position:
- Left Child wird mit (2 * i) + 1 bezeichnet .
- Rechtskind wird mit (2 * i) + 2 bezeichnet .
Und der Index des Elternteils eines Knotens im Index i kann bestimmt werden durch: (i - 1) / 2 .
Das SegmentTree- Array, das unser Beispiel darstellt, würde folgendermaßen aussehen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 3 | -1 | 0 | 3 | 6 |
+-----+-----+-----+-----+-----+-----+-----+
Schauen wir uns den Pseudo-Code an, um dieses Array zu erstellen:
Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
SegmentTree[position] := Item[low]
else
mid := (low+high)/2
constructTree(Item, SegmentTree, low, mid, 2*position+1)
constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if
Zuerst nehmen wir die Werte ein und initialisieren das SegmentTree- Array mit infinity
wobei die Länge des Item- Arrays als Größe verwendet wird. Wir rufen die Prozedur auf mit:
- low = Anfangsindex des Item- Arrays.
- high = Endindex des Artikel- Arrays.
- Position = 0 gibt die Wurzel unseres Segmentbaums an.
Versuchen wir nun die Vorgehensweise anhand eines Beispiels zu verstehen:
Die Größe unseres Item- Arrays beträgt 4 . Wir erstellen ein Array von Länge (4 * 2) - 1 = 7 und initialisieren sie mit infinity
. Sie können einen sehr großen Wert dafür verwenden. Unser Array würde folgendermaßen aussehen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Da dies eine rekursive Prozedur ist, wird der Betrieb des ConstructTree
mit einer Rekursionstabelle dargestellt, die bei jedem Aufruf calling line
low
, high
, position
, mid
und call aufzeichnet. Zuerst rufen wir ConstructTree (Item, SegmentTree, 0, 3, 0) auf . low
ist hier nicht gleich high
, wir bekommen eine mid
. Die calling line
gibt an, welcher ConstructTree
nach dieser Anweisung aufgerufen wird. Die ConstructTree
Aufrufe innerhalb der Prozedur bezeichnen wir als 1 bzw. 2 . Unser Tisch wird wie folgt aussehen:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
Wenn wir also ConstructTree-1
aufrufen, übergeben wir: low = 0
, high = mid = 1
, position = 2*position+1 = 2*0+1 = 1
. Sie können feststellen, dass 2*position+1
das linke Kind von root ist , also 1 . Da low
nicht gleich high
, bekommen wir eine mid
. Unser Tisch wird wie folgt aussehen:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
Beim nächsten rekursiven Aufruf übergeben wir low = 0
, high = mid = 0
, position = 2*position+1 = 2*1+1=3
. Wieder ist das linke Kind von Index 1 3 . low
ist hier e high
, also setzen wir SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1
. Unser SegmentTree- Array wird folgendermaßen aussehen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Unsere Rekursionstabelle wird wie folgt aussehen:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 0 | 3 | | |
+-----+------+----------+-----+--------------+
Sie sehen also, -1 hat seine korrekte Position erhalten. Da dieser rekursive Aufruf abgeschlossen ist, kehren wir zur vorherigen Zeile unserer Rekursionstabelle zurück. Der Tisch:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
In unserer Prozedur führen wir den Aufruf von ConstructTree-2
. Diesmal passieren wir low = mid+1 = 1
, high = 1
, position = 2*position+2 = 2*1+2 = 4
. Unsere calling line
ändert sich in 2 . Wir bekommen:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Da low
gleich high
, setzen wir: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2
. Unser SegmentTree- Array:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Unsere Rekursionstabelle:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
| 1 | 1 | 4 | | |
+-----+------+----------+-----+--------------+
Wieder sieht man, dass 2 seine korrekte Position hat. Nach diesem rekursiven Aufruf kehren wir zur vorherigen Zeile unserer Rekursionstabelle zurück. Wir bekommen:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Wir führen die letzte Zeile unserer Prozedur aus, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1
. Unser SegmentTree- Array:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | -1 | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Da dieser Rekursionsaufruf abgeschlossen ist, kehren wir zur vorherigen Zeile unserer Rekursionstabelle zurück und rufen ConstructTree-2
:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 2 |
+-----+------+----------+-----+--------------+
Wir können sehen, dass der linke Teil unseres Segmentbaums vollständig ist. Wenn wir auf diese Weise fortfahren, erhalten wir nach Abschluss der gesamten Prozedur endlich ein komplettes SegmentTree- Array. Das sieht dann so aus:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
Die Zeit- und Raumkomplexität beim Erstellen dieses SegmentTree- Arrays beträgt: O(n)
, wobei n die Anzahl der Elemente im Item- Array bezeichnet. Unser konstruiertes SegmentTree- Array kann zur Durchführung einer Range Minimum Query (RMQ) verwendet werden . Um ein Array zu erstellen, um die Range Maximum Query auszuführen, müssen wir die Zeile ersetzen:
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
mit:
SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])
Durchführen einer Bereichsminimalabfrage
Das Verfahren zur Durchführung eines RMQ ist bereits in der Einführung dargestellt. Der Pseudo-Code zum Prüfen der Range Minimum Query lautet:
Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high //Total Overlap
Return SegmentTree[position]
else if qLow > high || qHigh < low //No Overlap
Return infinity
else //Partial Overlap
mid := (low+high)/2
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if
qLow = The lower range of our query
. qHigh = The upper range of our query
. low = starting index of Item array
, high = Finishing index of Item array
, position = root = 0
. Versuchen wir nun, die Prozedur anhand des zuvor erstellten Beispiels zu verstehen:
Unser SegmentTree- Array:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
Wir möchten das Minimum im Bereich [1,3] finden .
Da dies eine rekursive Prozedur ist, wird die Operation des RangeMinimumQuery
mit einer Rekursionstabelle dargestellt, die qLow
, qHigh
, low
, high
, position
, mid
und calling line
qHigh
. Zunächst rufen wir RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0. Hier sind die ersten beiden Bedingungen nicht (teilweise Überlappung erfüllt). Wir werden erhalten mid
. Die calling line
gibt an, welche RangeMinimumQuery
danach genannt wird Wir bezeichnen die RangeMinimumQuery
Aufrufe innerhalb der Prozedur mit 1 bzw. 2. Unsere Tabelle sieht folgendermaßen aus:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Wenn wir also RangeMinimumQuery-1
aufrufen, übergeben wir: low = 0
, high = mid = 1
, position = 2*position+1 = 1
. Sie können feststellen, dass 2*position+1
das linke Kind eines Knotens ist . Das heißt, wir überprüfen das linke Kind von root . Da sich [1,3] teilweise [0,1] überschneidet, sind die ersten beiden Bedingungen nicht erfüllt, wir erhalten eine mid
. Unser Tisch:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Beim nächsten rekursiven Aufruf übergeben wir low = 0
, high = mid = 0
, position = 2*position+1 = 3
. Wir erreichen das linke Blatt unseres Baumes. Da [1,3] sich nicht mit [0,0] überschneidet, kehren wir infinity
zu unserer aufrufenden Funktion zurück. Rekursionstabelle:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 0 | 3 | | |
+------+-------+-----+------+----------+-----+--------------+
Da dieser rekursive Aufruf abgeschlossen ist, kehren wir zur vorherigen Zeile unserer Rekursionstabelle zurück. Wir bekommen:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
In unserer Prozedur führen wir einen RangeMinimumQuery-2
Aufruf aus. Diesmal passieren wir low = mid+1 = 1
, high = 1
und position = 2*position+2 = 4
. Unsere calling line changes to **2**
. Wir bekommen:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 2 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 1 | 1 | 4 | | |
+------+-------+-----+------+----------+-----+--------------+
Wir gehen also zum rechten Kind des vorherigen Knotens. Diesmal gibt es eine Gesamtüberlappung. Wir geben den Wert SegmentTree[position] = SegmentTree[4] = 2
.
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Zurück bei der aufrufenden Funktion überprüfen wir den Mindestwert der zwei zurückgegebenen Werte von zwei aufrufenden Funktionen. Offensichtlich ist das Minimum 2, kehren wir 2 an die aufrufende Funktion. Unsere Rekursionstabelle sieht so aus:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Wir sind mit dem linken Teil unseres Segmentbaums fertig. Nun rufen wir RangeMinimumQuery-2
von hier aus an. Wir passieren low = mid+1 = 1+1 =2
, high = 3
und position = 2*position+2 = 2
. Unser Tisch:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 2 | 3 | 2 | | |
+------+-------+-----+------+----------+-----+--------------+
Es gibt eine Gesamtüberlappung. Wir geben also den Wert zurück: SegmentTree[position] = SegmentTree[2] = 0
. Wir kehren zur Rekursion zurück, von der aus diese beiden Kinder aufgerufen wurden, und erhalten das Minimum von (4,0) , das heißt 0, und geben den Wert zurück.
Nach der Ausführung der Prozedur erhalten wir 0 , was das Minimum von Index- 1 bis Index- 3 ist .
Die Laufzeitkomplexität für dieses Verfahren ist O(logn)
wobei n die Anzahl der Elemente im Items- Array ist. Um eine Range Maximum Query durchzuführen, müssen wir die Zeile ersetzen:
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
mit:
Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
Lazy Propagation
Angenommen, Sie haben bereits einen Segmentbaum erstellt. Sie müssen die Werte des Arrays aktualisieren. Dies ändert nicht nur die Blattknoten Ihrer Segmentstruktur, sondern auch das Minimum / Maximum in einigen Knoten. Schauen wir uns das an einem Beispiel an:
Dies ist unser minimaler Segmentbaum mit 8 Elementen. Um Ihnen eine schnelle Erinnerung zu geben, repräsentieren alle Knoten den Mindestwert des daneben genannten Bereichs. Angenommen, wir möchten den Wert des ersten Elements unseres Arrays um 3 erhöhen. Wie können wir das machen? Wir werden dem Weg folgen, auf dem wir RMQ durchgeführt haben. Der Prozess würde folgendermaßen aussehen:
- Zuerst durchqueren wir die Wurzel. [0,0] überschneidet sich teilweise mit [0,7] , wir gehen in beide Richtungen.
- Bei linkem Teilbaum, [0,0] überschneidet sich teilweise mit [0,3] , wir gehen in beide Richtungen.
- Bei linkem Teilbaum, [0,0] überschneidet sich teilweise mit [0,1] , wir gehen in beide Richtungen.
- Im linken Teilbaum überschneidet sich [0,0] vollständig mit [0,0] . Da es sich um den Blattknoten handelt, aktualisieren wir den Knoten, indem er seinen Wert um 3 erhöht. Und den Wert -1 + 3 = 2 zurückgeben .
- Im rechten Teilbaum überlappt [1,1] nicht mit [0,0] , wir geben den Wert am Knoten ( 2 ) zurück.
Das Minimum dieser beiden zurückgegebenen Werte ( 2 , 2 ) beträgt 2 , daher aktualisieren wir den Wert des aktuellen Knotens und geben ihn zurück.
- Im rechten Teilbaum [2,3] überlappt sich nicht mit [0,0] , wir geben den Wert des Knotens zurück. ( 1 ).
Da der Mindestwert dieser beiden zurückgegebenen Werte ( 2 , 1 ) 1 ist , aktualisieren wir den Wert des aktuellen Knotens und geben ihn zurück.
- Bei linkem Teilbaum, [0,0] überschneidet sich teilweise mit [0,1] , wir gehen in beide Richtungen.
- Im rechten Teilbaum [4,7] überlappt sich nicht mit [0,0] , wir geben den Wert des Knotens zurück. ( 1 ).
- Bei linkem Teilbaum, [0,0] überschneidet sich teilweise mit [0,3] , wir gehen in beide Richtungen.
- Schließlich wird der Wert des Wurzelknotens aktualisiert, da das Minimum der beiden zurückgegebenen Werte (1,1) 1 ist .
Wir können sehen, dass das Aktualisieren eines einzelnen Knotens eine O(logn)
Zeitkomplexität erfordert, wobei n die Anzahl der Blattknoten ist. Wenn wir also aufgefordert werden, einige Knoten von i auf j zu aktualisieren, benötigen wir eine O(nlogn)
Zeitkomplexität. Dies wird bei einem großen Wert von n umständlich. Seien wir faul , arbeiten Sie nur, wenn Sie gebraucht werden. Wie? Wenn wir ein Intervall aktualisieren müssen, aktualisieren wir einen Knoten und markieren dessen untergeordnetes Element, dass es aktualisiert werden muss, und aktualisieren es bei Bedarf. Dafür brauchen wir ein Array Lazy, das genauso groß ist wie ein Segmentbaum. Anfänglich sind alle Elemente des Lazy- Arrays 0, was bedeutet, dass keine Aktualisierung ansteht. Wenn in Lazy [i] ein Element ungleich Null vorhanden ist, muss dieses Element den Knoten i im Segmentbaum aktualisieren, bevor Abfrageoperationen ausgeführt werden. Wie machen wir das? Schauen wir uns ein Beispiel an:
Sagen wir, für unseren Beispielbaum möchten wir einige Abfragen ausführen. Diese sind:
- [0,3] um 3 erhöhen .
- [0,3] um 1 erhöhen .
- [0,0] um 2 erhöhen .
[0,3] um 3 erhöhen:
Wir beginnen am Wurzelknoten. Zuerst prüfen wir, ob dieser Wert aktuell ist. Dazu prüfen wir unser Lazy- Array, das 0 ist, dh der Wert ist auf dem neuesten Stand. [0,3] überschneidet sich teilweise [0,7] . Wir gehen also in beide Richtungen.
- Im linken Teilbaum ist keine Aktualisierung anstehend. [0,3] überschneidet sich vollständig [0,3] . Wir aktualisieren also den Wert des Knotens um 3 . Der Wert wird also zu -1 + 3 = 2 . Dieses Mal werden wir nicht den ganzen Weg gehen. Anstatt nach unten zu gehen, aktualisieren wir das entsprechende Kind im Lazy-Tree unseres aktuellen Knotens und erhöhen es um 3 . Wir geben auch den Wert des aktuellen Knotens zurück.
- Im rechten Teilbaum ist kein Update anstehend. [0,3] überschneidet sich nicht [4,7] . Wir geben also den Wert des aktuellen Knotens zurück (1) .
Das Minimum von zwei zurückgegebenen Werten ( 2 , 1 ) ist 1 . Wir aktualisieren den Wurzelknoten auf 1 .
Unser Segmentbaum und Lazy Tree würde folgendermaßen aussehen:
Die Nicht-Null-Werte in den Knoten unseres Lazy Tree stellen dar, dass Aktualisierungen in diesen Knoten und darunter anstehen. Wir werden sie bei Bedarf aktualisieren. Wenn wir gefragt werden, was das Minimum im Bereich [0,3] ist , kommen wir zum linken Teilbaum des Wurzelknotens. Da keine Aktualisierungen ausstehen, geben wir 2 zurück , was korrekt ist. Daher beeinflusst dieser Prozess die Korrektheit unseres Segmentbaumalgorithmus nicht.
[0,3] um 1 erhöhen:
- Wir beginnen am Wurzelknoten. Es gibt keine ausstehende Aktualisierung. [0,3] überschneidet sich teilweise [0,7] . Wir gehen also in beide Richtungen.
- Im linken Teilbaum ist keine Aktualisierung anstehend. [0,3] überlappt vollständig [0,3] . Wir aktualisieren den aktuellen Knoten: 2 + 1 = 3 . Da es sich um einen internen Knoten handelt, werden die untergeordneten Elemente im Lazy Tree um 1 erhöht. Wir geben auch den Wert des aktuellen Knotens zurück ( 3 ).
- Im rechten Teilbaum ist keine Aktualisierung anstehend. [0,3] überschneidet sich nicht [4,7] . Wir geben den Wert des aktuellen Knotens zurück ( 1 ).
- Wir aktualisieren den Wurzelknoten, indem wir mindestens zwei zurückgegebene Werte ( 3 , 1 ) verwenden.
Unser Segmentbaum und Lazy Tree wird wie folgt aussehen:
Wie Sie sehen, sammeln wir die Updates bei Lazy Tree an, drücken sie aber nicht herunter. Dies ist was Lazy Propagation bedeutet. Wenn wir es nicht benutzt hätten, müssten wir die Werte bis zu den Blättern hinunterdrücken, was uns mehr Zeitaufwand kosten würde.
[0,0] um 2 erhöhen:
- Wir beginnen am Wurzelknoten. Da root aktuell ist und [0,0] teilweise überlappt [0,7] , gehen wir in beide Richtungen.
- Im linken Teilbaum ist der aktuelle Knoten auf dem neuesten Stand und [0,0] überschneidet sich teilweise mit [0,3] . Wir gehen in beide Richtungen.
- Im linken Teilbaum hat der aktuelle Knoten im Lazy Tree einen Wert ungleich Null. Es gibt also ein Update, das noch nicht auf diesen Knoten übertragen wurde. Wir werden diesen Knoten zuerst in unserem Segmentbaum aktualisieren. Das heißt also -1 + 4 = 3 . Dann werden wir diese 4 an ihre Kinder im Lazy Tree weitergeben. Da wir den aktuellen Knoten bereits aktualisiert haben, ändern wir den Wert des aktuellen Knotens in Lazy Tree auf 0 . Dann [0,0] teilweise überlappt [0,1], so gehen wir in beiden Richtungen.
- Am linken Knoten muss der Wert aktualisiert werden, da sich im aktuellen Knoten des Lazy Tree ein Wert ungleich Null befindet. Also aktualisieren wir den Wert auf -1 + 4 = 3 . Jetzt, da [0,0] total überlappt [0,0], aktualisieren wir den Wert des aktuellen Knotens zu 3 + 2 = 5. Dies ist ein Blattknoten, sodass wir den Wert nicht mehr weitergeben müssen. Wir aktualisieren den entsprechenden Knoten am Lazy Tree auf 0, da alle Werte bis zu diesem Knoten weitergegeben wurden. Wir geben den Wert des aktuellen Knotens zurück ( 5 ).
- Am rechten Knoten muss der Wert aktualisiert werden. Der Wert wird also zu: 4 + 2 = 6 . Da sich [0,0] nicht mit [1,1] überschneidet, wird der Wert des aktuellen Knotens ( 6 ) zurückgegeben. Wir aktualisieren auch den Wert in Lazy Tree auf 0 . Es ist keine Ausbreitung erforderlich, da dies ein Blattknoten ist.
Wir aktualisieren den aktuellen Knoten mit mindestens zwei zurückgegebenen Werten ( 5 , 6 ). Wir geben den Wert des aktuellen Knotens zurück ( 5 ).
- Am rechten Teilbaum steht ein Update an. Wir aktualisieren den Wert des Knotens auf 1 + 4 = 5 . Da dies kein Blattknoten ist, geben wir den Wert an seine Kinder in unserem Lazy Tree weiter und aktualisieren den aktuellen Knoten auf 0 . Da [0,0] sich nicht mit [2,3] überschneidet, geben wir den Wert unseres aktuellen Knotens ( 5 ) zurück.
Wir aktualisieren den aktuellen Knoten mit dem Minimum der zurückgegebenen Werte ( 5 , 5 ) und geben den Wert ( 5 ) zurück.
- Im linken Teilbaum hat der aktuelle Knoten im Lazy Tree einen Wert ungleich Null. Es gibt also ein Update, das noch nicht auf diesen Knoten übertragen wurde. Wir werden diesen Knoten zuerst in unserem Segmentbaum aktualisieren. Das heißt also -1 + 4 = 3 . Dann werden wir diese 4 an ihre Kinder im Lazy Tree weitergeben. Da wir den aktuellen Knoten bereits aktualisiert haben, ändern wir den Wert des aktuellen Knotens in Lazy Tree auf 0 . Dann [0,0] teilweise überlappt [0,1], so gehen wir in beiden Richtungen.
- Im rechten Teilbaum gibt es keine ausstehende Aktualisierung. Da sich [0,0] nicht mit [4,7] überschneidet, wird der Wert des aktuellen Knotens ( 1 ) zurückgegeben.
- Im linken Teilbaum ist der aktuelle Knoten auf dem neuesten Stand und [0,0] überschneidet sich teilweise mit [0,3] . Wir gehen in beide Richtungen.
- Wir aktualisieren den Wurzelknoten mit dem Minimum der beiden zurückgegebenen Werte ( 5 , 1 ).
Unser Segmentbaum und Lazy Tree wird wie folgt aussehen:
Wir können feststellen, dass der Wert bei [0,0] bei Bedarf alle Zuwächse erhielt.
Wenn Sie nun aufgefordert werden, das Minimum im Bereich [3,5] zu finden , wenn Sie bis zu diesem Punkt verstanden haben, können Sie leicht herausfinden, wie die Abfrage ablaufen würde, und der zurückgegebene Wert wird 1 sein . Unser Segment Tree und Lazy Tree würde folgendermaßen aussehen:
Wir haben einfach den gleichen Prozess befolgt, den wir bei der Suche nach RMQ befolgt haben, mit zusätzlichen Einschränkungen beim Überprüfen des Lazy Tree auf ausstehende Updates.
Eine andere Möglichkeit besteht darin, Werte von jedem Knoten zurückzugeben, da wir wissen, was der untergeordnete Knoten unseres aktuellen Knotens sein wird. Wir können sie einfach überprüfen, um das Minimum dieser beiden zu ermitteln.
Der Pseudo-Code für die Aktualisierung in Lazy Propagation lautet:
Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, high, position):
if low > high //out of bounds
Return
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
LazyTree[position] := 0
end if
if startRange > low or endRange < high //doesn't overlap
Return
end if
if startRange <= low && endRange >= high //total overlap
segmentTree[position] := segmentTree[position] + delta
if low is not equal to high
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1],
segmentTree[2 * position + 2])
Und der Pseudo-Code für RMQ in Lazy Propagation lautet:
Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
Return infinity
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
end if
LazyTree[position] := 0
end if
if qLow > high and qHigh < low //no overlap
Return infinity
end if
if qLow <= low and qHigh >= high //total overlap
Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
low, mid, 2 * position + 1),
RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
mid + 1, high, 2 * position + 1)