Segmentbaum: schnell und einfach

Am Vorabend des nächsten Starts des Kurses Algorithmen für Entwickler haben wir eine offene Lektion durchgeführt . Sie sprachen über die bekannte Idee eines Baums von Segmenten, diskutierten, wie man ihn erstellt, aktualisiert und schnell O(log n) die Summe der Zahlen eines beliebigen Segments eines gegebenen Arrays berechnet. Der Algorithmus ist sehr einfach und wirtschaftlich: Sie benötigen O(n) Speicher. Um das Material zu festigen, lösten sie das Olympiadenproblem.

---

Das Webinar wurde von einem erfahrenen Programmierer und Lehrer sowie dem Kursleiter "Algorithmen für Entwickler", Evgeny Volosatov, durchgeführt .

Das Sprichwort

Ein Segmentbaum ist eine Datenstruktur, die ein algorithmisch einfaches und logarithmisches schnelles Auffinden der Summe der Elemente eines Arrays in einem bestimmten Segment ermöglicht.

Stellen Sie sich zum Beispiel vor, Sie müssen die Summe der folgenden Zahlen finden:



Außerdem müssen wir nicht nur die Summe der Zahlen der angegebenen Folge (die Summe der Elemente eines bestimmten Arrays) berechnen, sondern so schnell wie möglich die Summe einer Folge dieser Zahlen finden . Das heißt, wir können ein Intervall (Segment) abfragen und die Antwort so schnell wie möglich geben. Wie lautet die Summe der Zahlen aus diesem Intervall:



Was bedeutet es schnell? Das geht schneller, als wenn wir die Zahlen einfach aufsummieren . Immerhin kann es Millionen und Abermilliarden von Zahlen geben ...

Es war der Wunsch, schnell die Summe der aufeinander folgenden Elemente zu finden, die die Motivation für unser Webinar waren. Darüber hinaus geht es nicht nur um die Summe, sondern auch um andere Aufgaben, beispielsweise die Berechnung einer assoziativen Funktion. Es handelt sich also um Operationen, deren Ausführung nicht von der Berechnungsreihenfolge abhängt.

Kehren wir zu unserer Zeile zurück:



Wenn wir das Ergebnis schnell finden möchten, müssen wir natürlich einige Beträge im Voraus berechnen. Das erste, was mir in den Sinn kommt, ist das paarweise Falten:



Wenn Sie nun die Summe der Zahlen ermitteln müssen, können wir dies fast sofort tun. Um beispielsweise die Summe des oben genannten Segments zu ermitteln, müssen Sie lediglich 13 bis 9 addieren. Alles ist elementar: Um die Summe der vier Zahlen zu ermitteln, haben wir nur zwei addiert.

Wir erschweren die Aufgabe:



Um die Summe dieses Segments zu ermitteln, müssen wir die Elemente addieren, die auf die eine oder andere Weise unser Segment abdecken:



Natürlich 3 + 13 + 19 = 35. Um die Summe der sieben Zahlen zu ermitteln , haben wir nur drei addiert. Wenn das Segment aus tausend Elementen bestand, würde es ausreichen, durchschnittlich 10 Elemente hinzuzufügen, da wir eine logarithmische Komplexität mit einem Logarithmus zur Basis 2 haben.

Voller binärer Baum

Ein vollständiger binärer Baum ist ein Baum, von dem jedes Element genau zwei untergeordnete Elemente hat.

Um mit einem vollständigen Binärbaum zu arbeiten, können und sollten Sie eine Datenstruktur wie ein Array verwenden. Die Nummerierung dieses Arrays ist von eins bequem . Wir nummerieren jedes Element des Binärbaums mit natürlichen Zahlen von 1 bis 2 ⁿ -1:



Das Schöne an diesem Ansatz ist, dass es sehr einfach ist, die Anzahl der Kinder und Eltern zu berechnen.
Die Formel zur Berechnung des "linken Kindes": i * 2 , das "rechte": i * 2 + 1 .



Zum Beispiel berechnen wir die Anzahl der Kinder im fünften Element:

1. 5 x 2 = 10 ;
2. 5 x 2 + 1 = 11 .

Und wie kommt es vom „Kind“ zum „Elternteil“? Wir verwenden die Ganzzahldivision i / 2

Ok, und wie kann man feststellen, ob das Kind links oder rechts ist? Die Antwort lautet wie folgt: Linke Kinder haben gerade Zahlen, rechte Kinder haben ungerade Zahlen .

Merke dir diese Punkte.

Wir kehren zu unserem Beispiel eines binären Baums zurück und fragen uns, wie wir ihn bauen können. Schauen Sie, wir haben zuerst eine Reihe von Zahlen:



Dafür müssen Sie einen Binärbaum erstellen. Wie viel Speicher wird benötigt, um den Binärbaum zu speichern, an dessen Ende sich diese Elemente befinden?

Die Antwort auf diese Frage lautet 2n, wenn n eine Zweierpotenz ist.

Wir gehen weiter, weil zwei weitere Fragen vor uns auftauchen:

1. Aus welchem ​​Element müssen die Quellnummern in einem Array eines vollständigen Binärbaums platziert werden?
2. Aus welchem ​​Element und in welcher Richtung werden wir beginnen, unseren Baum mit vorberechneten Mengen zu füllen?

Die Antwort auf die erste Frage ist ganz einfach: Wir haben 8 Elemente, insgesamt gibt es 16 Elemente im Array, was bedeutet, dass das erste Element mit 16 - 8 = 8 nummeriert wird. Und wir beginnen mit dem Bauen von links nach rechts und von unten nach oben, beginnend mit Element 7, Werte bei Kindern addieren, so:



Als nächstes müssen Sie festlegen, wie die Summe des gewünschten Segments ermittelt werden soll. Kehren wir zu unserem ersten Beispiel zurück, nummerieren Sie die Elemente und definieren Sie ein Segment. Wir bezeichnen das erste Element in dem Segment, das mit dem Buchstaben L hinzugefügt werden soll, und das letzte mit R:



Jetzt ist es notwendig, ein weiteres Konzept einzuführen, damit der Algorithmus der Aktionen klar ist. Wir sprechen über das Konzept der Grundelemente und ihrer entsprechenden Grundsegmente. Das fundamentale Element ist ein beliebiges Element aus dem gesamten Array, und das fundamentale Segment entspricht diesem Element, d. H. Den Elementen aus dem anfänglichen Array, die seine unmittelbaren Kinder / Enkel sind. Für das Grundelement mit der Nummer 4 "5" wird das Grundsegment von 8 bis 9 Element sein: ["2"; "3"]:



Das Grundelement mit der Nummer 10 - „7“ (wir haben es als L bezeichnet) fällt mit seinem Grundsegment zusammen. Ist es möglich, dieses grundlegende Segment zu erweitern, ohne LR zu überschreiten? In unserem Fall können Sie. Die Regel für den linken Rand lautet: Wenn es sich um ein linkes untergeordnetes Element handelt, kann das grundlegende Segment erweitert werden. Das neue grundlegende Element ist das übergeordnete Element des aktuellen Segments. Das heißt, wir können Folgendes in das Programm schreiben:



Gehen wir nun zum rechten Element R über. Es ist ein grundlegendes Element und ein linkes Kind, sodass wir den Bereich nicht mehr erweitern können (wir gehen über das Segment hinaus). Daher können wir der Antwort dieses Element hinzufügen:



Als Nächstes müssen Sie das linke Element nach rechts und das rechte nach links verschieben. Für das linke Element mit dem Index L = 10 ist der nächste Index 5, da er an das übergeordnete Element geht. Aber es wird zuerst nach rechts und dann nach oben gehen:



Also bewegte sich der Wert von L auf ein höheres Niveau und ein wenig nach rechts. Wie wird R abnehmen? Mit der Formel (R - 1) / 2.



Hier ist ein solcher Algorithmus. Die folgenden Werte der Variablen L und R werden wie folgt verschoben:



Wenn der Baum nicht 8 Elemente enthält, sondern eine ungünstige Zahl, z. B. 12, müssen wir den Baum (der Binärbaum muss vollständig sein) zu 16 hinzufügen.
Die Formel zur Berechnung der Anzahl der Elemente (der gesamte Teil des Logarithmus wird genommen):



Nun berechnen wir die assoziative Funktion des Findens des Minimums . Hier ist unser Baum und schneiden:



Wie oft wird Ihrer Meinung nach Element 5 an unserer Funktion beteiligt sein - eins oder zwei? Natürlich, aber wie wird das im Algorithmus überprüft? Tatsächlich ist dieses Element entweder ein linker oder ein rechter Sohn, was bedeutet, dass die Aktion entweder für L oder R ausgeführt wird.


+

Betrachten Sie nun die Änderungsoperation. Angenommen, ein Element hat sich geändert, anstelle von 7 ist 0 eingegangen. Damit unser Segmentbaum funktionsfähig bleibt, müssen wir alle übergeordneten Elemente aktualisieren und ganz nach oben gehen.

Lösung des Olympiadenproblems

Eine der Voraussetzungen für solche Aufgaben ist, dass alles schnell gehen soll. Wir haben also folgende Bedingung:



Wir werden es mit dem Wissen über den Baum der Segmente lösen. Als Ergebnis erhalten wir den folgenden C # -Code:



Wir senden es zur Überprüfung, wir sehen, dass die Entscheidung getroffen wurde und vollständig ist , was bedeutet, dass unser Algorithmus funktioniert.



Das ist alles, wenn Sie mehr Details möchten, schauen Sie sich das gesamte Video an . Sie können auch in Ruhe die folgenden Artikel des Autors von unserem Lehrer Evgeny Volosatov über Habré lesen :

- Balancieren von rot-schwarzen Bäumen - Drei Fälle ;
- Das Pferd bewegt sich auf Bits. Schach Bitboard .