[GO] Python-Implementierung eines nicht rekursiven Segmentbaums

Einführung

Wie der Titel schon sagt, möchte dieser Artikel Ihnen die ** nicht rekursive Segment Tree ** -Implementierung von ** Python ** vorstellen. Ich werde mit der Erklärung von ** Segment Tree ** beginnen, damit ich nicht die erforderlichen Kenntnisse "fast" [^ 1] benötige. Wenn Sie es also bereits kennen, überspringen Sie es bitte. → [Implementierung eines nicht rekursiven Segmentbaums](# Implementierung eines nicht rekursiven Segmentbaums)

[^ 1]: Sie müssen das Konzept der Berechnung und der Python-Notation verstehen.

Was ist ein Segmentbaum?

Eine Datenstruktur, die allgemein als ** Segmentbaum **, ** Segmentbaum ** usw. bekannt ist, ein Array mit der Länge $ N $ {$ a_i $} $ _ {i = 0} ^ {N-1} $ Andererseits können die folgenden zwei Operationen in Bezug auf ** Monoid ** $ • $ mit einem Zeitberechnungsbetrag von $ O (logN) $ ausgeführt werden.

• $ update (i, x) $: Ändern Sie $ a_i $ in $ x $
• $ query (l, r) $: Gibt $ a_l • a_ {l + 1} • $… $ • a_ {r-1} $ für das halboffene Intervall $ [l, r) $ zurück

Unter Berücksichtigung der allgemeinen Addition als ** Monoid ** ist $ query (l, r) $ die Summe der Intervalle von $ a_l $ bis $ a_ {r-1} $, dh $ \ Sigma_ {i = l} Entspricht dem Ergebnis von ^ {r-1} a_i $.
Beachten Sie, dass ** monoid ** ein Operator $ • $ ist, der die folgenden Bedingungen erfüllt.

• Für jedes $ a, b, c $, $ (a • b) • c = a • (b • c) $ (** Gesetz beitreten **)
• Ein bestimmtes $ e $ existiert und für jedes $ a $ ist $ e • a = a • e = a $ (** Einheitselement existiert **)

Beispiele für ** Monoide ** sind Additionen und Multiplikationen, $ min $ und $ max $.

Im Folgenden wird ** Segment Tree ** anhand des Zusatzes $ + $ als Beispiel für ** Monoid ** erläutert.
Zunächst eine einfache Implementierung in Betracht ziehen:

def update(i, x):
    a[i] = x

def query(l, r):
    res = 0
    for i in range(l, r):
        res += a[i]
    return res

Diese Zeitberechnungen sind schnell, wobei $ update (i, x) $ $ O (1) $ ist, aber langsam, weil $ query (l, r) $ $ O (N) $ ist.
Betrachten Sie nun die in der folgenden Abbildung gezeigte Datenstruktur. (Zusammenfassend ist dies kein anderer als ** Segment Tree **.)

• Die Zahlen in [] geben den Index in ** Segment Tree ** an, und die fetten Zeichen geben die Werte der enthaltenen Daten an.
  Durch Verwendung dieses ** Segmentbaums ** erhöht sich der Rechenaufwand für $ update (i, x) $ auf $ O (logN) $, aber der Rechenaufwand für $ query (l, r) $ beträgt auch $ O ( Sie können es auf logN) $ ablegen.

Für $ query (1, 7) $ finden Sie beispielsweise die Summe der grauen Teile in der folgenden Abbildung. Um ehrlich zu sein, müssen Sie nur 5 Mal, aber nur 3 Mal hinzufügen.

Ich werde keinen detaillierten Beweis liefern, da ich die Implementierung hauptsächlich erläutern möchte, aber für jede Kombination von $ l, r (l <r) $ funktioniert $ query (l, r) $ mit $ O (logN) $. Ich werde.
Lassen Sie uns nun über die Implementierung sprechen (** rekursiv **). Der Einfachheit halber ist es auf $ N = 8 $ festgelegt, aber das Gleiche gilt für andere Fälle als $ 8 $.

Implementierung des Updates (i, x)

Für $ update (i, x) $ sind die zu aktualisierenden Werte $ a_i $ (unterste Ebene in der obigen Abbildung), $ a_i + a_j $ (zweite Ebene von unten), $ a_i + a_j + a_k + a_l $ (3. Schicht von unten), $ a_i + a_j + a_k + a_l + $… (4. Schicht von unten) Es gibt insgesamt vier. Diese Zahl ist $ O (logN) $, da sie der Höhe des Baums entspricht, wenn ** Segmentbaum ** als vollständige Zweiteilung betrachtet wird.

Wenn die Indizes wie oben gezeigt eingestellt sind, sind die Indizes mit den zu aktualisierenden Werten in der richtigen Reihenfolge. i+N-1, ((i+N-1)-1)/2, (((i+N-1)-1)/2-1)/2, ((((i+N-1)-1)/2-1)/2-1)/2 Es ist geworden. ($ / $ Wird abgerundet und geteilt.) Ich werde es auch hier nicht im Detail erklären, aber Sie können sehen, dass ** Segment Tree ** eine vollständige Dichotomie ist.

Aus dem Obigen ergibt sich die Implementierung von $ update (i, x) $ wie folgt.

def update(i, x):
    i += N-1 #Index in der untersten Ebene
    dat[i] = x

    #Aktualisieren Sie die Werte beim Klettern auf Ebenen
    while i > 0:
        i = (i-1) >> 1 #Index der nächsthöheren Schicht(Eltern in völliger Zweiteilung)

        #Ersetzen Sie die Summe der beiden unteren Schichten(Summe der Kinder in einer vollständigen Zweiteilung)
        dat[i] = dat[i*2+1] + dat[i*2+2]

Implementierung der Abfrage (l, r)

$ query (l, r) $ sollte hinzugefügt werden, wenn der "Wert des Intervalls, das bestimmten Daten zugewiesen wurde" vollständig in $ [l, r) $ passt. Daher können Sie mit ** rekursiv ** wie folgt schreiben.

#Rekursive Funktionsabfrage(l, r, k, L, R)
# L :Sektion[L,R)Linker Rand von(Anfangswert 0), R :Sektion[L,R)Rechtes Ende von(Anfangswert N.)
# k :Sektion[L,R)Index mit dem Berechnungsergebnis für(Anfangswert 0)

def query(l, r, k=0, L=0, R=None):
    #R-Initialisierung
    if R is None:
        R = N

    #Wenn Abschnitt[l,r)Und Abschnitt[L,R)Gibt 0 zurück, wenn sich nicht überschneidet
    if R <= l or r <= L:
        return 0

    #Sektion[L,R)Ist der Abschnitt[l,r)Gibt diesen Wert zurück, wenn er perfekt passt
    if l <= L and R <= r:
        return dat[k]

    #Zu anderen Zeiten tauchen Sie in den Baum und sehen Sie die beiden Kinder
    else:
        lres = query(l, r, k*2+1, L, (L+R) >> 1)
        rres = query(l, r, k*2+2, (L+R) >> 1, R)
        return lres + rres

Zusammenfassung der Implementierung des Segmentbaums (rekursiv)

Basierend auf dem oben Gesagten wird der Segmentbaum wie folgt implementiert. Dies ist eine Implementierung für allgemeine Monoide.

class SegmentTree:
    #Initialisierungsprozess
    # f :Monoid auf Segmentbaum
    # default :Einheitselement für f
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() #Stellen Sie der Einfachheit halber die Anzahl der Elemente N auf 2 ein
        self.default = default
        self.dat = [default]*(self.size*2-1) #Elemente in Einheiten initialisieren
        self.f = f

    def update(self, i, x):
        i += self.size-1
        self.dat[i] = x
        while i > 0:
            i = (i-1) >> 1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, l, r, k=0, L=0, R=None):
        if R is None:
            R = self.size
        if R <= l or r <= L:
            return self.default
        if l <= L and R <= r:
            return self.dat[k]
        else:
            lres = self.query(l, r, k*2+1, L, (L+R) >> 1)
            rres = self.query(l, r, k*2+2, (L+R) >> 1, R)
            return self.f(lres, rres)

Implementierung eines nicht rekursiven Segmentbaums

Dies ist übrigens eine ziemlich lange Einführung, und das Hauptthema ist von hier. Der obige ** SegmentTree ** verwendet eine ** rekursive Funktion **, ist also etwas langsam. Daher wird die Implementierung durch ** nicht rekursive Funktion ** nützlich.

Es kann mit der gleichen Struktur wie für rekursiv implementiert werden, ist jedoch viel einfacher zu implementieren, indem der Index um 1 auf ** 1-indiziert ** verschoben wird. Wenn ** 1-indiziert ** eingestellt ist, entspricht der Index der Abbildung unten.

Wenn Sie es ** 1-indiziert ** machen, können Sie die in der folgenden Tabelle gezeigte Beziehung für einen Knoten $ i $ erhalten. Diese Beziehung ist nützlich für die Implementierung.

def update(i, x):
    i += N #Index in der untersten Ebene
    dat[i] = x

    #Aktualisieren Sie die Werte beim Klettern auf Ebenen
    while i > 0:
        i >>= 1 #Index der nächsthöheren Schicht(Eltern in völliger Zweiteilung)
        #Ersetzen Sie die Summe der beiden unteren Schichten(Summe der Kinder in einer vollständigen Zweiteilung)
        dat[i] = dat[i*2] + dat[i*2+1]

Für einen Knoten liegt der dargestellte Abschnitt innerhalb von $ [l, r) $, und wenn sich der vom übergeordneten Knoten dargestellte Abschnitt in Richtung ** links ** erstreckt, ist der Knoten ein untergeordnetes Element auf der ** rechten ** Seite. Es hat einen Index von ** ungerade **. Wenn er sich dagegen in der ** rechten ** Richtung erstreckt, ist der Knoten ein untergeordnetes Element auf der ** linken ** Seite, sodass er einen Index von ** gerade ** hat.

Klettern Sie daher für die linke Seite von unten auf den Baum. Wenn sich der übergeordnete Abschnitt darüber hinaus erstreckt (wenn der Index des aktuell angezeigten Knotens ** ungerade ** ist), fügen Sie den Wert dieses Knotens hinzu und fügen Sie einen Index hinzu. Sie müssen nur den Vorgang des Verschiebens nach rechts wiederholen. Gleiches gilt für die rechte Seite. Wenn sich der übergeordnete Abschnitt darüber hinaus erstreckt, kann er hinzugefügt und der Index um eine nach links verschoben werden. Da es jedoch im ** halboffenen Abschnitt ** angezeigt wird, wird beurteilt, ob es sich ausdehnt, basierend darauf, ob der Index des aktuell angezeigten Knotens ** ungerade ** ist. Beachten Sie auch, dass der Knoten ** 1 übrig ** hinzugefügt wird.

Das Implementierungsbeispiel lautet wie folgt.

def query(l, r):
    #Initialisieren Sie, um in der untersten Ebene zu indizieren
    l += N
    r += N

    #Initialisieren Sie die Antwort links und die Antwort rechts mit 0
    lres, rres = 0, 0

    #Führen Sie die Addition mit dem obigen Urteil durch, bis sich l und r überlappen
    while l < r:
        #Wenn l ungerade ist, dat[l]Hinzufügen
        if l & 1:
            lres += dat[l]
            l += 1

        #Wenn r ungerade ist, dat[r-1]Hinzufügen
        if r & 1:
            r -= 1
            rres += dat[r]

        #Auf einen Baum klettern
        l >>= 1
        r >>= 1

    res = lres + rres
    return res

class SegmentTree:
    #Initialisierungsprozess
    # f :Monoid auf Segmentbaum
    # default :Einheitselement für f
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() #Stellen Sie der Einfachheit halber die Anzahl der Elemente N auf 2 ein
        self.default = default
        self.dat = [default]*(self.size*2) #Elemente in Einheiten initialisieren
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) #Beachten Sie die Berechnungsrichtung, da das Umrechnungsgesetz für Monoide nicht garantiert ist.
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

Vergleich

Wir haben die Ausführungszeiten anhand von Problemen verglichen, die mit ** Segment Tree ** gelöst werden können. Die Ergebnisse sind in der folgenden Tabelle aufgeführt und bestätigen, dass nicht rekursiv in kürzerer Zeit ausgeführt werden kann.

** Problem URL ** AOJ DSL_2_A http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A

AOJ DSL_2_B http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

AtCoder ABC_125_C https://atcoder.jp/contests/abc125/tasks/abc125_c

** Einreichungs-URL ** AOJ DSL_2_A (rekursiv) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326213#1

AOJ DSL_2_A (nicht rekursiv) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326214#1

AOJ DSL_2_B (rekursiv) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326207#1

AOJ DSL_2_B (nicht rekursiv) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326206#1

AtCoder ABC_125_C (rekursiv) https://atcoder.jp/contests/abc125/submissions/11596118

AtCoder ABC_125_C (nicht rekursiv) https://atcoder.jp/contests/abc125/submissions/11596126

Schließlich

Weit entfernt von Qiita habe ich zum ersten Mal in meinem Leben einen Artikel geschrieben, also denke ich, dass er voller Dinge ist. Wenn Sie Fragen wie "das ist seltsam" oder "etwas Seltsames ist geschrieben" haben, melden Sie dies bitte.