Was ist dieser Artikel?

Die Verwendung von Segmentbäumen kann als Methode zum schnellen Erhalten der k-ten kleinsten Zahl aus einer Menge betrachtet werden, in der Zahlen hinzugefügt oder gelöscht werden. Zuerst habe ich diese Erklärung nicht gut verstanden, also habe ich sie weggeworfen.

Vorausgesetztes Wissen

RSQ mit Segmentbaum. Das Folgende ist sehr leicht zu verstehen. Obwohl es sich um eine Erklärung von RMQ handelt, ist die Idee für Min und Sum zu 95% gleich. https://www.creativ.xyz/segment-tree-entrance-999/

RSQ selbst ist keine Datenstruktur, deren Zweck es ist, den k-ten kleinsten Wert zu erhalten, aber dies kann mit hoher Geschwindigkeit unter Verwendung von RSQ erreicht werden.

Das Problem, das Sie lösen möchten

ARC033C: Datenstruktur

Verarbeiten Sie die folgende Abfrage für den Satz von Zahlen S. --Typ 1: Fügen Sie die Nummer X zu S hinzu. `` --Typ 2: Beantworte die X. kleinste Zahl in S und entferne diese Zahl aus S. ``
Einschränkungen: 1 <= N, <= 200.000 --Punkt 1: Die gleiche Nummer wird nicht zu S hinzugefügt

Punkt

N ist ein relativ kleiner Wert. Diese Einschränkung ist auf die Speicherbeschränkung beim Erstellen eines Segmentbaums von $ len (N) $ und die Einschränkung zurückzuführen, dass O (N) bei der Initialisierung immer angewendet wird.

Dichotomie des Segmentbaums RSQ

Betrachten Sie als Beispiel die drittkleinste Zahl aus $ [2, 3, 5, 7] $.

Setzen Sie zunächst den Wert im Segmentbaum mit $ index $ jeder Zahl auf $ 1 $. (Innerhalb des Quadrats in der Abbildung) Angesichts der Abfrage RSQ $ [0, i) $ sieht es wie der Wert unter dem Feld aus.

Wenn wir uns das ansehen, können wir sehen, dass das erste (ganz links) i, für das die Abfrage $ [0, i) $ = k ist, der Wert ist, den wir erhalten möchten (die k-te kleinste Zahl).

Wenn Sie $ i $ erhalten, das die am weitesten links stehende Abfrage $ [0, i) $ = k erfüllt, ist es offensichtlich, dass der Index von i der Wert ist, den Sie erhalten möchten. Im Folgenden wird diese Methode betrachtet.

Methode 1: Führen Sie die Abfrage in einer 2-minütigen Suche aus, um das am weitesten links stehende k O zu finden (log ^ 2 N).

Zunächst kann die in der Erläuterung von ARC033 beschriebene Methode betrachtet werden.

Unter Ausnutzung der Tatsache, dass der für RSQ erforderliche Rechenaufwand höchstens O (logN) beträgt, ist es möglich, mit der Abfrage [0, N) zu beginnen und eine dichotomieähnliche Abfrage [0, mid] durchzuführen, um den Index ganz links zu erhalten. Es ist realistisch.

Bei dieser Methode wird der RSQ-Berechnungsbetrag $ O (logN) $ mit dem Dichotomie-Berechnungsbetrag $ O (logN) $ multipliziert, sodass die Summe $ O (log ^ 2N) $ beträgt.

def segmentTreeBisectLeft(segTreeTarget: segmentTreeSum, x):
    lo, hi = 0, st.lenOriginalList
    while lo < hi:
        mid = (lo+hi)//2
        if segTreeTarget.query(0, mid + 1) < x: lo = mid + 1 #RSQ hier[0,mid)Abfrage
        else: hi = mid
    return lo

Methode 2: Graben Sie einen Segmentbaum mit einer 2-minütigen Suche, um das am weitesten links stehende k O (log N) zu finden.

Betrachten Sie hier find (x, n), das anhand der Baumstruktur des Segmentbaums nach dem kleinsten x sucht, das unter Knoten n verwaltet wird. Als nächstes wird anhand des obigen Eingabebeispiels die Operation angezeigt, bei der Sie die drittkleinste Zahl kennen möchten, und jede Operation wird beschrieben.

--1: Eingabe in Wurzelknoten 0 (find (3, 0) -2: Übergabe find (3, 1) an linken Knoten 1 —— 3: Wenn der Knoten einen kleineren Wert als das empfangene x hat, subtrahiert er den Wert des Knotens und gibt ihn an seinen übergeordneten Knoten zurück. Im Beispiel wird x = 3 minus seiner eigenen 2 an Knoten 0 zurückgegeben. Dies liegt daran, dass Sie keinen Knoten unter Ihrer Kontrolle finden möchten, wenn Sie die x-kleinste Zahl finden möchten, aber nur x-a-Knoten unter Ihrer Kontrolle verwalten möchten. --4: Wurzelknoten 0 gibt 1 von Knoten 1 links zurück. Verwenden Sie diesen Wert also, um find (1, 2) an Knoten 2 rechts zu senden. --5. Knoten 2 sendet find (1,5) an Knoten 5 auf der linken Seite. ―― 6. Knoten 5 sendet find (1, 11) an Knoten 11 auf der linken Seite. Dieses Blatt hat keinen Wert und gibt daher None zurück. ―― 7. Knoten 5 sendet find (1, 12) an Knoten 11 auf der linken Seite. ―― 8: Dieses Blatt entspricht x. Dies gibt index = 5 zurück. Dies erforderte, dass die Funktion den k-ten kleinsten Wert von 5 hatte.

def findNthValueSub(self, x, nodeId):
    """
    [2, 3, 5, 7] = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0]
Funktion zum Abrufen des x-ten kleinsten Werts im Segmentbaum, der zugeordnet ist
    """
    #Von hier an erfolgt die Verarbeitung zu Knoten, die keine Blätter sind
    if self.dat[nodeId] < x: #Wenn dieser Knoten einen Wert hat, der kleiner als angefordert ist
        return (None, x - self.dat[nodeId])
    if nodeId >= self.lenTreeList - 1: #Wenn nodeIf ein Knoten ist
        return (True, nodeId - (self.lenTreeList - 1)) #Gibt die Indexnummer zurück
    resLeft = self.findNthValueSub(x, 2 * nodeId + 1) #Suche links
    if resLeft[0] != None: #Wenn es einen Wert gibt, geben Sie ihn zurück
        return (True, resLeft[1])
    resRight = self.findNthValueSub(resLeft[1], 2 * nodeId + 2) #Suchen Sie rechts
    return resRight

Ausführliche Erklärung

https://www.slideshare.net/chokudai/arc033 https://ei1333.hateblo.jp/entry/2017/12/14/000000

Ganzer Quellcode

https://github.com/recuraki/PythonJunkTest/blob/master/atcoder/lib/treeSegment/segmentTreeSum.py

[PYTHON] Ermitteln Sie die n-kleinste Zahl aus dem Array mit O (logN) mithilfe eines Segmentbaums