[GO] [Fenwick_Tree] AtCoder Library liest mit einem grünen Codierer ~ Implementierung in Python ~

0. Einleitung

AtCoder Offizielle Algorithmus-Sammlung AtCoder Library (** ACL **), veröffentlicht am 7. September 2020 es war erledigt. Ich fand das eine gute Gelegenheit, da die meisten in ACL aufgezeichneten Algorithmen und Datenstrukturen für mich neu waren. Deshalb habe ich alles getan, vom Studium der Algorithmen bis zur Implementierung in Python.

In diesem Artikel werden wir uns ** Fenwick_Tree ** (** Phoenix Tree **) ansehen.

Zielgruppe Leser

• Wenn Sie sich den ACL-Code ansehen, aber ** nicht wissen, was Sie tun **.
• Diejenigen, die C ++ nicht verstehen und es in Python lesen möchten.

Nicht zielgerichtete Leser

• Diejenigen, die Python-optimierten Code für ACL möchten. → Da es so implementiert wurde, dass es so weit wie möglich mit ACL identisch ist, wird die Ausführungsgeschwindigkeit in Python überhaupt nicht berücksichtigt. Es scheint eine Bewegung zu geben, die es direkt von Cython aus zur Verfügung stellt, daher kann es gut sein, dem zu folgen.

Referenziert

Über den Mechanismus des Phönixbaums

• Binär indizierter Baum (Folie) Sehr einfach zu verstehen
• [Wikipedia --Phoenix Tree](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF % E6% 9C% A8)

Über die Bitoperation

• Python-Bit-Operation
• Wikipedia-2-Ergänzung

1. Was ist ein Phönixbaum?

Um zu verstehen, was ein Phönixbaum ist, betrachten wir zunächst die folgenden Fragen.

Bei einer Folge von $ N $ in der Länge $ a_1, a_2, \ cdots, a_N $ werden viele der folgenden zwei Arten von Abfragen gegen diese Folge geworfen: Bitte behandeln Sie dies.

• ** add **: Da $ i und x $ angegeben sind, addiere $ x $ zu $ a_i $.
• ** sum **: Da $ i $ angegeben ist, wird die Summe vom Anfang bis zum $ i $ th berechnet.

Im Folgenden kann der angegebene Wert explizit als add (i, x), sum (i) geschrieben werden.

1.1 Zunächst eine einfache Antwort

Denken Sie zunächst genau so, wie es im Problem geschrieben steht. Abfrage hinzufügen

a_i \leftarrow a_i+x

Daher kann es mit dem Berechnungsbetrag $ O (1) $ verarbeitet werden. Auf der anderen Seite die Abfragesumme

a_1+a_2+\cdots+a_i

Muss berechnet werden, daher beträgt der Berechnungsbetrag $ O (N) $.

1.2. Apropos Teilsumme, kumulative Summe

Wenn Sie von Teilsummen von Zahlen wie Abfragesummen sprechen, können Sie sich kumulative Summen vorstellen. Tatsächlich kann die Abfragesumme mit $ O (1) $ verarbeitet werden, wenn Sie ein Array vorbereiten, das die kumulative Summe der Zahlenspalten $ a $ ist. Aber was ist mit der Abfrage hinzufügen? Wenn Sie einen Teil der Sequenz $ a $ ändern, müssen Sie die kumulierte Summe neu berechnen, sodass der Berechnungsbetrag am Ende $ O (N) $ beträgt.

1.3. Phönixbaum zu diesem Zeitpunkt

Sowohl die einfache Antwort als auch die kumulative Summe erforderten einen Berechnungsbetrag von $ O (N) $, um sowohl Additions- als auch Summenabfragen zu verarbeiten. Natürlich wäre es schön, wenn das genug wäre, aber ich möchte es schneller machen. .. .. ** Phoenix Tree ** erscheint zu solchen Zeiten. Phoenix Tree kann jedes Mal ** ** von add add und sum ** für $ O (\ log N) $ verarbeiten! ** ** ** Phönixbäume werden auch als ** Binary Indexed Tree (BIT) ** bezeichnet.

2. Was für ein Baum ist ein Phönixbaum?

Werfen wir einen Blick auf die Struktur des Phönixbaums. Betrachten wir daher den Fall, in dem $ N = 7 $ speziell die Länge der Sequenz $ a $ ist.

2.1 Machen Sie vorerst einen Baum

Da es sich um eine Baumstruktur handeln sollte, da sie als "Baum" des Phönix bezeichnet wird, erstellen wir einen Baum aus der Sequenz $ a $. Insbesondere wird, wie in der folgenden Abbildung gezeigt, ein Baum mit jedem Begriff in der Sequenz als Blatt und der Summe der beiden Begriffe als übergeordnetes Element erstellt.

Nachdem wir nun einen Baum (Wald?) Haben, verwenden wir diesen Baum, um die Probleme im vorherigen Kapitel zu lösen. Zuerst wird die Abfrage hinzugefügt. Erwägen Sie beispielsweise, $ a_3 $ zu aktualisieren. Es gibt drei Stellen, an denen $ a_3 $ in Beziehung steht, sodass Sie diese aktualisieren können. Im Allgemeinen müssen so viele Stellen aktualisiert werden wie die Höhe eines Baumes. Die Höhe dieses Baums beträgt ungefähr $ \ log N $, daher beträgt der Berechnungsbetrag $ O (\ log N) $. Wie wäre es mit der Abfragesumme? Zum Beispiel, wenn Sie die Summe bis zum 7. finden

\sum_{i=1}^{7}{a_i}=(a_1+a_2+a_3+a_4)+(a_5+a_6)+(a_7)

Sie sollten sich also 3 Stellen ansehen. Im Allgemeinen müssen Sie nur die Höhe des Baums betrachten, sodass der Berechnungsbetrag $ O (\ log N) $ beträgt.

2.2 Klüger

Es scheint also, dass $ O (\ log N) $ sowohl für Additions- als auch für Summenabfragen verwendet werden kann. Ich möchte sagen, dass ich glücklich bin, aber der Baum, den ich früher gemacht habe, ist tatsächlich verschwenderisch. Tatsächlich gibt es einige Stellen, die ich noch nie gesehen habe, als ich alle Summen bis zur ersten, die Summe bis zur zweiten, $ \ cdots $ und die Summe bis zur siebten überprüfe. Nach dem Entfernen sieht es wie in der Abbildung unten aus. Es enthält alle Informationen, die zur Verarbeitung der Abfragesumme erforderlich sind. (Die Abfrage hinzufügen aktualisiert nur den relevanten Speicherort, sodass kein Problem vorliegt.)

2.3 Das wahre Aussehen des Phönixbaums

Bisher habe ich der Baumstruktur gezeigt, dass sie weiß, "welche Art von Baum ist ein Phönixbaum?". Wenn Sie sich jedoch den Code des Phönixbaums in ACL ansehen, ist er eindimensional mit einer Länge von $ N $ von "Daten". Es gibt nur ein Array. Wo ist der Baum? Tatsächlich sind diese "Daten" mit einer Baumstruktur gepackt. Insbesondere enthält es ** Informationen zu "Anweisungen, denen zu folgen ist" unter Verwendung des Index des Arrays **. Lassen Sie uns nun den Baum, den wir oben gesehen haben, in ein eindimensionales Array ändern. Wie Sie vielleicht bemerkt haben, beträgt der verbleibende Platz nur $ N $, wenn Sie den unnötigen Teil früher entfernen. Und der Maximalwert des Index, der die Teilsumme annimmt (rot unterstrichener Teil in der folgenden Abbildung), ist an jeder Stelle unterschiedlich. Mit diesem Wert können Sie "Daten" erstellen.

Also fand ich heraus, dass die Realität des Phoenix-Baums (in Bezug auf die Implementierung) ein eindimensionales Array ** ist, das auf nette Weise mit Teilsummen gefüllt ist.

3. Wie man in einer seltsamen Anordnung geht

Unser Ziel ist es, Abfragen zu verarbeiten, die mit diesem seltsamen Array "Daten" addiert und summiert werden. In diesem Kapitel werden wir uns ansehen, wie jede Abfrage Ihnen "** Anweisungen zum Folgen **" gibt.

3.1. Abfrage hinzufügen

Zuerst wird die Abfrage hinzugefügt. Die Abfrage add (i, x) kann an eine beliebige Stelle gehen, die $ a_i $ enthält. Schauen wir uns einige Beispiele an.

Es ist schwer, die Regeln mit genau dem zu sehen. Wenn Sie jedoch auf den "Unterschied zwischen dem aktuellen Index und dem nächsten Index" achten, wird sich der Ausblick sofort verbessern.

Die roten Buchstaben sind die Indizes von "Daten", die grünen Pfeile sind die Richtungen und die grünen Buchstaben sind die Indexunterschiede. Wenn Sie sich diese Abbildung ansehen, sehen Sie, dass Sie +1 von unten und +2 von der Mitte hinzufügen können. Der obere, mittlere und untere Teil dieser Figur werden durch "die Anzahl der zu summierenden Terme" geteilt, und dies wird als "** Länge **" bezeichnet. Zum Beispiel ist "Länge der Daten [6]" 2. Um die Abfrage add (i, x) zu verarbeiten, können wir Folgendes sagen:

Index

i^\prime = i + (data[i]Länge von)

Und füge x zu data [i] hinzu.

3.2 Abfragesumme

Schauen wir uns als nächstes die Abfragesumme an. Die Abfragesumme (i) sollte verfolgt werden, um $ a_1, \ cdots, a_i $ abzudecken, und summiert werden. Achten wir wie bei der zuvor hinzugefügten Abfrage auf den "Unterschied zwischen dem aktuellen Index und dem nächsten Index".

Schließlich können Sie mit "Länge" den nächsten Index finden. Um die Abfragesumme (i) zu verarbeiten, können wir daher Folgendes sagen:

Index

i^\prime = i - (data[i]Länge von)

Nehmen Sie während der Aktualisierung die Summe aller Daten [i].

3.3. Länge

Es stellt sich heraus, dass beide Abfragen verarbeitet werden können, solange die "Länge der Daten [i]" erhalten wird. Wie erhält man die Länge von data [i] von i? Denken Sie daran, dass der Phönixbaum auch als binär indizierter Baum bekannt ist. Zeigt den Index und seine binäre Anzeige für jede Länge an.

In dieser Tabelle entspricht die Länge "** der Index wird binär angezeigt und die Stelle, an der '1' zum ersten Mal angezeigt wird, wenn er von rechts betrachtet wird ", dh " das niedrigstwertige Bit von '1' **". Sie können sehen, dass. Das niedrigstwertige Bit wird häufig in englischer Sprache als ** Least Significant Bit (LSB) ** geschrieben. Und "LSB von '1' in i" (geschrieben als = LSB (i)) kann leicht durch ** Bitoperation ** erhalten werden.

LSB(i) \quad=\quad i\quad\&\quad(-i)

Wobei & eine bitweise UND-Verknüpfung ist. Bitoperationen für negative Zahlen werden als [2-Komplement] ausgedrückt (https://ja.wikipedia.org/wiki/2%E3%81%AE%E8%A3%9C%E6%95%B0) Es wird wie dargestellt durch (Referenz) behandelt. Schauen wir uns einige Beispiele an. Hier betrachten wir die 8-Bit-2-Komplementdarstellung. Wenn $ i = 6 $

\begin{aligned}
LSB(6) &= 6 \quad\&\quad(-6)\\
&= (00000110)_2 \quad\&\quad (11111010)_2\\
&= (00000010)_2\\
&= 2
\end{aligned}

Wenn $ i = 7 $

\begin{aligned}
LSB(7) &= 7 \quad\&\quad(-7)\\
&= (00000111)_2 \quad\&\quad (11111001)_2\\
&= (00000001)_2\\
&= 1
\end{aligned}

Wenn $ i = 24 $

\begin{aligned}
LSB(24) &= 24 \quad\&\quad(-24)\\
&= (00011000)_2 \quad\&\quad (11101000)_2\\
&= (00001000)_2\\
&= 8
\end{aligned}

Jetzt, da Sie bereit sind, Phoenix Tree zu implementieren, können Sie es implementieren.

4. Implementierung

Lassen Sie es uns implementieren. Implementieren Sie Variablennamen, Methodennamen usw. so weit wie möglich gemäß ACL.

4.1 Konstruktor

Erstellen Sie die Klasse Fenwick_Tree, um den Konstruktor zu implementieren.

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n  #Elementanzahl
        self.data = [0] * n

Behalten Sie die Anzahl der Elemente in der Instanzvariablen "_n" bei und erstellen Sie eine Liste "Daten" mit der Länge n. Zum Zeitpunkt der Initialisierung ist alles 0. Dies entspricht der Folge $ a = \ {0, \ cdots, 0 \} $. Wenn Sie mit einer Zeichenfolge ungleich Null initialisieren möchten, führen Sie $ add (i, a_i) $ für jedes i aus.

Hinweis Bis zum vorherigen Kapitel war data ** 1-indiziert **, in der Implementierung jedoch ** 0-indiziert **. Bitte beachten Sie, dass der Phoenix-Baum-Mechanismus 1-indiziert ist, sodass Sie ihn beim Zugriff auf "Daten" um 1 verschieben müssen.

4.2. add Lassen Sie uns zuerst von der Methode add implementieren. Diese Methode entspricht der Abfrage add (p, x).

def add(self, p, x):
    assert 0 <= p < self._n
    p += 1  # 0-indexed -> 1-indexed
    while p <= self._n:
        self.data[p - 1] += x　 #Daten aktualisieren
        p += p & -p  #LSB bis p(p)Hinzufügen

Wie wir in Kapitel 3.1 gesehen haben, findet Query Add den nächsten Index, der durch Hinzufügen von LSB angezeigt werden soll. Wiederholen Sie diese Indexaktualisierung und Datenaktualisierung, bis nicht mehr auf das Array verwiesen wird.

4.3. sum Als nächstes folgt die Methodensumme. In ACL wird die der Abfragesumme (i) entsprechende als interne (private) Funktion implementiert, und die tatsächlich verwendete externe (öffentliche) Funktion ist allgemeiner. Es ist implementiert. Insbesondere durch Angabe von zwei Werten l und r wird die Teilsumme der linksgeschlossenen und rechtsoffenen halboffenen Abschnitte [l, r]

\sum_{i = l}^{r - 1}{a_i}

Kehrt zurück. (a ist 0-indiziert) Implementieren Sie zunächst aus der internen Funktion, die der Abfragesumme entspricht. Dies gibt die Teilsumme $ a_0 + \ cdots + a_ {r --1} $ des halboffenen Intervalls [0, r) für r zurück. Es wird jedoch 0 zurückgegeben, wenn $ r = 0 $ ist. Ich habe am Anfang auch einen Unterstrich (_) hinzugefügt, um anzuzeigen, dass es sich um eine interne Funktion handelt.

def _sum(self, r):
    s = 0  #Variable, um die Summe zu setzen
    while r > 0:
        s += self.data[r - 1]
        r -= r & -r  #r zu LSB(r)Subtrahieren
    return s

Wie wir in Kapitel 3.2 gesehen haben, weiß die Abfragesumme, welcher Index als nächstes betrachtet werden muss, indem das LSB subtrahiert wird. Nehmen Sie während der Aktualisierung die Summe aller "Daten [r]". Verwenden Sie diese interne Funktion, um die oben erwähnte generische externe Funktion zu implementieren.

def sum(self, l, r):
    assert 0 <= l <= r <= self._n
    return self._sum(r) - self._sum(l)

([l, r)Teilsumme von) = (r -Teilsumme bis 1) - (l -Teilsumme bis 1)

ist.

4.4. Zusammenfassung

fenwicktree.py

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n
    
    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)
    
    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

5. Anwendungsbeispiel

Es ist ursprünglich nicht notwendig, aber wir fügen direkt zu a hinzu, um die Sequenz a selbst zu sehen.

    n = 8 
    a = [0, 1, 2, 3, 4, 5, 6, 7]
    fw = Fenwick_Tree(n)
    for i, a_i in enumerate(a): fw.add(i, a_i)  #Initialisieren Sie mit der Zahlenspalte a
    print(fw.sum(2, 4))  # 5
    print(fw.sum(6, 7))  # 6 sum(i, i + 1)In einem[i]Kann erhalten werden
    fw.add(2, 6)  # a[2] += 6
    a[2] += 6
    fw.add(5, -1)  # a[5] += -1
    a[5] += -1
    print(a)  # [0, 1, 8, 3, 4, 4, 6, 7]
    print(fw.sum(0, 3))  # 9
    print(fw.sum(3, 7))  # 17

6. Problembeispiel

AtCoder Library Practice Contest B "Fenwick Tree"

7. Schlussfolgerung

Von der Aufklärung des Mechanismus des Phönixbaums bis zur Implementierung in Python. Der Phönixbaum scheint verschiedene Anwendungen zu haben, deshalb würde ich ihn gerne eines Tages studieren.

Bitte lassen Sie uns wissen, wenn Sie Fehler, Bugs oder Ratschläge haben.