Einführung

Wenn ich AtCoder mache, sehe ich oft starke Leute, die auf Twitter twittern, wie zum Beispiel das Einfügen eines Seg-Baums, aber da ich ihn selbst nicht hatte, ist es ein Artikel, den ich zu diesem Zeitpunkt implementieren und mit Verständnis und Anwendung verbinden werde. ..

Wenn Sie gerade am Wettbewerb teilnehmen und ihn sofort implementieren möchten, enthält die Implementierungszusammenfassung Code. Der Betrieb kann nicht garantiert werden.

Es tut mir leid zu sagen, welche Zahl der Sud ist. Ich denke daran, mich zu differenzieren, indem ich die Implementierung von Narutake nicht auslasse.

Machen Sie es zur grundlegendsten Struktur der Ein-Punkt-Aktualisierung und Abschnittserfassung. Ich werde in der Fortsetzung über die Bewertung von Verzögerungen schreiben, wenn ich Lust dazu habe (oder wenn ich es brauche).

Referenzierte Websites

http://beet-aizu.hatenablog.com/entry/2017/09/10/132258 https://www.slideshare.net/iwiwi/ss-3578491 http://tsutaj.hatenablog.com/entry/2017/03/29/204841

Was ist ein Segmentbaum?

Was kann ich tun?

Sie können ** O (logN) ** verwenden, um Intervallabfragen zu Operationen und Operationen zu finden, die bestimmte Eigenschaften erfüllen. (Zum Beispiel eine Abfrage, um den Mindestwert des ersten oder fünften Elements zu ermitteln.) Beachten Sie jedoch, dass zum Erstellen ** O (N) ** erforderlich ist.

Welche Art von Berechnung kann dann verwendet werden?

Alles, was als ** Monoid ** bezeichnet wird, kann eingebettet werden.

Was ist ein Monoid?

Ich denke, es ist ein bisschen weniger streng,

Es reicht aus, wenn die Bindungsregel gilt und das Einheitselement vorhanden ist.

Was ist das Gesetz der Verbindung?

Zum Beispiel, wenn Sie über Addition nachdenken

(a+b)+c = a+(b+c)

Auf diese Weise ** ist es gut, wenn sich das Ergebnis nicht ändert, unabhängig davon, wo Sie bei der Berechnung zwischen drei oder mehr Dingen rechnen ** Da dies zutrifft, kann der Segmentbaum den Abschnitt durch Erfassen des Werts immer mehr teilen. ([0,6) → (wie [0,4) + [4,6))

Was ist ein Einheitselement?

Es ist schwierig, das Original zu sagen, aber in Bezug auf die Anwendung, wenn Sie in Bezug auf die Ergänzung denken,

a + 0 = 0+ a = a

** Eine Zahl, die mit der ursprünglichen Zahl identisch ist, wenn sie damit berechnet wird, wird als Einheitselement bezeichnet ** Außerdem zum Beispiel, wenn Sie über Multiplikation nachdenken

a \cdot 1 = 1 \cdot a = a

1 ist das Einheitselement.

Beispiele für Monoide

Berechnung	Einheitselement
Zusatz	0
Multiplikation	1
Mindestwert	INF ※1
Maximalwert	-INF ※2
Minimales gemeinsames Vielfaches	1

1 Kurz gesagt, wenn ein Wert verwendet wird, der höher als der Wert ist, der angezeigt werden kann, wird er zu einem Einheitselement. Wenn zum Beispiel die Einschränkung des Problems $ A_i <= 10 ^ 4 $ ist, wenn das Einheitselement $ 10 ^ 4 + 1 $ ist, ist $ min (A_i, 10 ^ 4 + 1) = min (10 ^ 4 + 1,) A_i) = A_i $, welches das Einheitselement ist. Wenn das Ziel nur natürliche Zahlen sind, gibt es kein Einheitselement.
2 Wenn in einer Diskussion ähnlich dem Fall des Minimalwerts ein Wert verwendet wird, der kleiner oder gleich dem Wert ist, der erscheinen kann, wird er zu einem Einheitselement.

Ich denke, dass spezielle Operationen abhängig von anderen Einschränkungen als Monoide behandelt werden können, aber ich denke nicht, dass Leute, die sich solche Ideen einfallen lassen, diesen Artikel lesen müssen, also werde ich ihn verlassen.

[Referenz] http://beet-aizu.hatenablog.com/entry/2017/09/10/132258

Was ist das für eine Struktur?

Eine Halbierende mit den Ergebnissen einer Abfrage in dem abzudeckenden Abschnitt. Als Array implementieren.

セグ木.png

So was. Je tiefer Sie gehen, desto kleiner wird der Abschnitt.

Bitte achten Sie auf den Index des Arrays. ** Sie können den untergeordneten Index über den übergeordneten Index x2 und den übergeordneten Index x2 + 1 abrufen. ** Es ist grundlegend für BIT (Binary Index Tree) und gegabelte Bäume, aber ich war beeindruckt, als ich es zum ersten Mal sah. Das liegt übrigens daran, dass ich mit 1-Index denke, und wenn es 0-Index ist, wird es × 2 + 1, × 2 + 2. Es spielt keine Rolle, welchen Sie verwenden, aber ich persönlich verwende 1-Index, da die Betrachtung des Elternteils vom Kind nur um 2 unterbrochen werden muss.

Hier enthält das untere Blatt die Originaldaten der Sequenz, die Sie abfragen möchten. (Diesmal ist es ein Array der Größe 4)

Was ist, wenn die Anzahl der Elemente im Array nicht 2 ^ k beträgt?

Bestimmen Sie die Tiefe des Baums, damit die Anzahl der Blätter am unteren Rand so gut vorbereitet werden kann wie die interessierende Sequenz, für die die Intervallabfrage ursprünglich berechnet wurde. Der überschüssige Teil sollte mit dem Einheitselement gefüllt werden.

Lassen Sie es uns ein wenig ändern und ein Beispiel für die Arraygröße = 3 betrachten. Wenn Sie das Einheitenelement ausfüllen, das oben im verbleibenden Teil angezeigt wurde,

Auf diese Weise kann es ohne besonderen Einfluss verarbeitet werden.

Implementierung

Initialisieren

Bestimmen Sie die Größe des Arrays, in dem der Baum gespeichert ist, so dass die Anzahl der Blätter am Ende 2 ^ k beträgt und Sie mehr als die Größe des Arrays sichern können, das Sie abfragen möchten.

1+2+4+8+\cdots+2^n = 2^{n+1} -1

Angesichts dessen

2 ^ k> = (Datenarraygröße)

Bereiten Sie für k ein Baumspeicherarray mit einer Größe von $ 2 ^ {k + 1} $ vor. Die Implementierung sieht so aus.

class segtree:

    def __init__(self, n,operator,identity):
        """
        n:Datenarraygröße
        operator:Operator(Monoid).. Funktionsobjekt
        identity:Einheitselement entsprechend dem Operator
        """
        nb = bin(n)[2:] #In Binär konvertieren und 0b im Kampf entfernen
        bc = sum([int(digit) for digit in nb]) #Die Zahl mit 1 in Bit. Wenn dies 1 ist, ist es nur 2^nb.Wenn nicht, 2^nb<n<2^(nb+1)
        if bc == 1: #2^mit nb
            self.num_end_leaves = 2**(len(nb)-1) #Das untere Blatt ist 2^nb Stücke
        else:#Wenn nicht 2^(nb+1)Sichern
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)] #Mit Einheitselement initialisieren

        self.identity = identity 
        self.operator =operator
        #Haben Sie Einheitenelemente und Operatoren für die spätere Verwendung

Wert aktualisieren

Ich habe es am Anfang kurz geschrieben, aber wenn es 1-Index ist, wenn Sie Ihren Index durch 2 teilen und ihn abschneiden, werden Sie Ihr Elternteil. (Wie 3 → 1, 5 → 2)

Der Wert wird aktualisiert, indem dieser auf den Ursprung zurückgeführt und die Operatoren der Reihe nach angewendet werden. Die Implementierung nur dieses Teils sieht so aus.

    def update(self,x,val):
        """
        x:Substitutionsort
        val:Wert zu ersetzen
        """
        actual_x = x+self.num_leaves #1-Fügen Sie die Minute hinzu, in der der Index des Blattes am Ende des Index beginnt(Wenn beispielsweise die Datenarraygröße 4 beträgt, beträgt die Baumarraygröße 8, und die zweite Hälfte beginnt mit Index 4.
        self.array[actual_x] = val #Wert aktualisieren
        while actual_x > 0 :
            actual_x = actual_x//2#Siehe Eltern
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])#Aktualisieren Sie die Eltern mit einem neuen Kind

Wert erhalten

Für einen bestimmten Bereich ist es nur erforderlich, den Bereich durch Kombinieren von Blättern ausdrücken zu können, die einen möglichst großen Bereich abdecken. Zum Beispiel, wenn Ihr Datenarray 4 groß ist und Sie einen Bereich von [0,2] möchten.

So was

Wenn Ihr Verantwortungsbereich außerhalb der Abfrage liegt, schauen Sie sich das Kind an.
Wenn der Abfragebereich Ihren Verantwortungsbereich umfasst, geben Sie den Wert zurück.
Wenn die Position nicht mit der Abfrage zusammenhängt, wird das Element unit zurückgegeben.

Wenn Sie in diesem Fall [0,1], [2] wiederholen, wird das Einheitselement als Wert erhalten, und es fühlt sich an, als würden diese Unterregionen zusammengeführt.

Operator ([0,1], [2], Einheitselement) = Operator ([0,1], [2]) = Operator ([0,2])

Sie können eine Intervallabfrage erhalten. Die Implementierung ist so.

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        q_links: Links vom Abfrageabschnitt
        q_right:Rechts vom Abfrageintervall
        arr_ind:Index des Baumarrays. Erstens ist ein Elternteil so 1
        leaf_left:Links vom Baumarray-Index der Bereich, der von den Blättern abgedeckt wird, die er darstellt
        depth:Tiefe in einem Baumarray. Wird verwendet, um die Größe der Abdeckung zu berechnen
        """
        width_of_floor = self.num_end_leaves//(2**depth) #Deckbreite des aktuellen Blattes
        leaf_right = leaf_left+width_of_floor-1 #Suchen Sie die rechte Seite der aktuellen Blattabdeckung vom linken Rand und der Abdeckungsbreite.

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity #Gibt das Einheitselement zurück, wenn der Abfragebereich und das Blatt nicht miteinander verbunden sind

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind] #Wenn der Abfragebereich vollständig mit Blättern gefüllt ist, geben Sie den Wert der Blätter zurück

        else: #Wenn nicht, schauen Sie sich das Kind an
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)#Kind ist links
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)#Kind hat recht
            return self.operator(val_l,val_r)#Führt eine Operation zum Zusammenführen von untergeordneten Elementen aus.

Implementierungszusammenfassung

Falten, weil ich gerade die vorherigen geklebt habe

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

Versuch

Erstellen Sie ein geeignetes Bereichsarray und fragen Sie nach dem Mindestwert. Planen Sie außerdem die Ausführungszeit entsprechend.

s_tree = segtree(10**5,min,10**9) #10**Da es sich um ein Array mit bis zu 5 handelt, ist das Einheitselement 10**9
arr = [i for i in range(10**5)]

print(datetime.datetime.now())

for i,a in enumerate(arr):
    s_tree.update(i,a)

print(datetime.datetime.now())


print(s_tree.get(0,10**4))
print(s_tree.get(3*10**4,5**10**4))
print(s_tree.get(2,7*10**4))

print(datetime.datetime.now())

2020-02-04 19:15:34.934814
2020-02-04 19:15:35.646339
0
30000
2
2020-02-04 19:15:35.646587

Immerhin ist der Bau der schwerste. Die Bedienung scheint normal zu sein. (Es scheint, dass der Fehler behoben ist, wenn Sie ihn nicht mit einem komplizierteren Problem verschieben.)

Der Versuch, Segmentbäume Schritt für Schritt zu implementieren und zu verstehen (Python)