Datenstruktur für die Behandlung geschlossener Intervalle

Dies kann in O gelöst (log ^ 2 n) Zeit und O (n log n) Raum eine Kombination aus einer Fenwick Baum und Strukturdaten auf der Grundlage eines Segmentbaum , die einen internen Baum in jedem Knoten enthält . Ersteres wird verwendet, um Zählungen von Punkten innerhalb eines gegebenen Bereichs effizient zu finden und zu aktualisieren; letzteres für das effiziente Finden und Aktualisieren von Zählungen von Segmenten, die einen bestimmten Punkt überspannen. Die Grundidee besteht darin, Segmentendpunkte innerhalb des angegebenen Abfragebereichs zu zählen und anschließend für Segmente anzupassen, die einen oder beide Endpunkte kreuzen.

Dieser Algorithmus basiert auf der Beobachtung, dass für einen bestimmten Abfragebereich (a, b)

  

nKontakt = (h - nStraddlingOne) / 2

wobei nContained die Anzahl von Intervallen ist, enthalten ist, durch (a, b), h die Anzahl von Intervall Endpunkten jeder Art (Anfang oder Ende) in (a, b), und nStraddlingOne ist die Anzahl der Intervalle, die entweder enthalten nur ein oder nur b. Die "Datenbank" der Intervalle zu jeder Zeit heißt hier D.

Ein Fenwick-Baum erlaubt Ihnen, die Gesamtzahl der Punkte zwischen zwei ganzzahligen Indizes (a, b) in O (log n) -Zeit unter Verwendung einer O (n) -Tabelle zu zählen. Es erlaubt auch O (log n) Insertionen und Deletionen. Wir fügen beide Endpunkte jedes Intervalls hinzu und berechnen daraus h in O (log n) -Zeit.

Zählübergänge

Unsere andere Datenstruktur ist sehr ähnlich zu einem Segmentbaum, aber es gibt zwei wesentliche Unterschiede: Statt die Start- und Endpunkte der Intervalle von dem Eingang des Folgerns von Intervallen, wir die Menge der Endpunkte nehmen jede mögliche ganze Zahl zu sein zwischen 1 und n einschließlich, und keine "offenen Mengen" haben (dies soll das Hinzufügen neuer Intervalle später vereinfachen); und wir speichern das Intervall jedes Knotens auf eine bestimmte Art und Weise.

Nehmen Sie zur Vereinfachung an, dass n eine Potenz von 2 ist (wenn nicht, wählen Sie einfach die nächstgrößere Potenz von 2 - dies wird eine Zunahme von weniger als n verursachen, so dass sich die zeitliche Komplexität nicht ändert). Sei T ein kompletter binärer Baum, der für jede Position einen Blattknoten hat & lt; = i & lt; = n. (Dieser Baum hat insgesamt 2n - 1 Knoten.) Jeder Blattknoten repräsentiert eine einzelne Position. Jeder Nicht-Blatt-Knoten repräsentiert die Vereinigung der Positionen aller Blattknoten darunter, die ein Intervall mit der Länge einer Potenz von 2 bilden müssen. Nennen Sie das Intervall, das durch einen Knoten v Int (v) repräsentiert wird. (Anmerkung: Da dieser Binärbaum vollständig ist, kann er "implizit" dargestellt werden, wie es häufig bei einem binären Heap geschieht, um Speicherplatz zu sparen.)

Jedem Knoten v von T entspricht eine Menge von Intervallen, die als Span (v) bezeichnet werden. (Wir speichern nur ihre äußersten rechten Endpunkte.) Span (v) ist die Menge aller Intervalle in D, die

1. Enthält Int (v) und
2. Enthält nicht Int (übergeordnetes Element (v)).

In jedem Eckpunkt v, speichern wir nur die am weitesten rechts liegenden Endpunkten der Intervalle in Span (v) in einem selbstausgleich Binärbaum , die von diesem Endpunkt bestellt werden, und in dem jeder Knoten erweitert mit einer Anzahl von Nachkommenknoten. Das heißt, jeder Knoten des "äußeren" Baums enthält einen "inneren" Baum. Dies ist notwendig, um effizient berechnen zu können, wie viele Intervalle ein bestimmtes Abfrageintervall vollständig enthalten.

Die grundlegende Abfrageoperation in einem Segmentbaum bestimmt die Menge von Intervallen, die einen gegebenen Punkt x enthalten, und dies wird leicht geändert, um einzelne Intervalle zu zählen statt sie zu berichten. Die Operation ist einfach: Setzen Sie v auf die Wurzel,

1. Fügen Sie die Anzahl der Intervalle in Span (v) zur Summe hinzu.
2. Wenn v ein Blatt ist, dann hör auf.
3. Angenommen, die linken und rechten Kinder von v sind jeweils u und w. Wenn x in Int (u) enthalten ist, dann rekuriere auf u, andernfalls rekursiere auf w.

Gegeben ein Abfrageintervall (a, b), die obige Abfrage kann zweimal ausgeführt werden, einmal für a und einmal für b. Setze nStraddlingAtLeastOne auf die Summe der Zählwerte für beide Abfragen. Beachten Sie, dass die Zählung in O (1) -Zeit für jeden Knoten erfolgen kann - es ist nur das Zählfeld des Wurzelknotens des selbstabgleichenden Binärbaums, der Span (v) speichert.

Doppelkreuzungen!

Die Schwierigkeit (und was schließlich einen früheren Versuch einer O stymied (log n) Algorithmus, dass ich einige Zeit damit verbracht auf), ist, dass wir müssen auch die Anzahl der Intervalle zählen, die gleichzeitig Spanne beide Endpunkte der Abfrage (a, b). Um dies zu tun, beginnen wir mit v an der Wurzel erneut und führen eine modifizierte Abfrage für a (den Startpunkt der Abfrage) durch, in der Schritt 1 ersetzt wird durch:

1. Zählen Sie die Anzahl der Intervalle in Span (v) mit dem rechten Endpunkt & gt; = b, und fügen Sie sie zum Gesamtwert hinzu.

Dieser Zählschritt kann aufgrund des selbstabgleichenden Binärbaums in der Zeit O (log n) durchgeführt werden.Da jede Baumebene bis zu 2 dieser Zählvorgänge benötigt, ist dies der Teil, der die Zeitkomplexität auf O (log ^ 2 n) hochdrückt. Setzen Sie nContaining auf die Summe aus dieser Abfrage. Wir können nStraddlingOne mit

  

nStraddlingOne = nStraddlingAtLeastOne - nContaining

Mit Hilfe von nStraddlingOne und dem vom Fenwick-Baum berechneten h können wir jetzt nContained nach der obigen Gleichung berechnen.

Hinzufügen und Entfernen von Intervallen

Die Aktualisierung ist auch O (log ^ 2 n), da das Aktualisieren des Fenwick-Baums O (log n) ist und das Hinzufügen eines Intervalls (x, y) zum Segmentbaum die Zeit O (log ^ 2 n) unter Verwendung der folgender Algorithmus, beginnend mit v an der Wurzel:

1. Wenn (x, y) Int (v) enthält, fügen Sie y zum selbstbalancierenden Binärbaum hinzu, der die rechten Endpunkte von Span (v) speichert und stoppt.
2. Angenommen, die linken und rechten Kinder von v sind jeweils u und w.
   • Wenn (x, y) Int (u) überlappt, rekrutiere auf u.
   • Wenn (x, y) Int (w) überlappt, rekursieren Sie auf w.

Das obige Traversal besucht nur O (log n) -Knoten im Segmentbaum, da jedes hinzugefügte Intervall in den Intervallmengen von höchstens 2 Knoten auf jeder Baumebene für maximal 2log (n) Platzverbrauch pro erscheint Intervall. Für einen Nachweis und weitere Erläuterungen siehe die Wikipedia-Seite zu Segment Trees . Das Entfernen eines Intervalls verwendet einen ähnlichen Algorithmus. Jedes Einfügen oder Entfernen in den selbstabgleichenden Binärbaum an einem Knoten dauert O (log n) -Zeit, für O (log ^ 2 n) insgesamt.

Speicherplatznutzung

Die Speicherplatzbelegung ist O (nlog n), da in der Segmentstruktur O (log n) Baumebenen vorhanden sind, die jeweils Platz für 2 Instanzen eines internen Baumknotens mit jedem möglichen Endpunkt benötigen. Beachten Sie insbesondere, dass, obwohl es O (n ^ 2) mögliche unterschiedliche Intervalle gibt, nur der äußerste rechte Endpunkt jedes Intervalls gespeichert wird. Dies ist also kein Problem. Auch weil wir Zählungen speichern, führt das Hinzufügen einer zweiten Kopie eines vorhandenen Intervalls nur zu einer Erhöhung der Zählungen - es werden keine neuen Knoten zugewiesen. Fenwick Bäume benutzen nur O (n) Raum.

Siehe Bereichsbaum . Die Zeitkomplexität für die Abfrage wird als O erwähnt (log ^d n + k). Hier ist d die Dimension, n ist die Anzahl der im Baum gespeicherten Punkte und k ist die Anzahl der von der Abfrage berichteten Punkte.

Aber wir brauchen nur die Anzahl, ohne die Punkte zu melden. Also denke ich, wenn die Anzahl der Kinder (tatsächlich die Anzahl der Blätter, weil die realen Punkte in den Blättern gespeichert sind) auf jedem Knoten beibehalten wird, kann dieses k eliminiert werden, was uns O zurückgibt (log ² n). Insertion und Deletion sind ebenfalls O (log ² n).

Ein Intervallbaum passt hier, zum Beispiel Ссылка sehen Sie diesen Code, er bietet einen findContained was aussieht O (log (n)), Abgesehen davon ist die Löschung komplexer, aber sicherlich kann in O (log (n)) getan werden Ссылка

Manchmal können einfache sortierte Mengen verwendet werden:
- Die Intervalle im Datensatz haben eine bekannte maximale Länge.
- Und zusätzlich ist diese maximale Länge nicht zu groß im Vergleich zum gesamten Wertebereich von x Datenpunkten im Set.

In diesem Fall genügt es, einfach eine sortierte Menge zu verwenden:
- Fügen Sie Intervalle hinzu, indem Sie nur x dimension des Intervalls verwenden.
- Fragen Sie es wie folgt ab: get intervals with their x dimension in range [x', y'] and then filter out the few intervals that have their y dimension crossing the y' limit .

Angesichts derselben oben erwähnten Vorbedingung für Dateneigenschaften mit bekannter maximaler -Länge kann diese Logik erweitert werden, um auch baumähnliche Abfragen durchzuführen, wo die Abfrage dies nicht tut Fragen Sie nach "Daten rein enthalten innerhalb des Intervalls", sondern stattdessen nach "Daten überlappend das angegebene Intervall". In diesem Fall wäre die Abfrage:
- get intervals with their x dimension in range [x' - maximum interval range, y' + maximum interval range] and then filter out the few intervals that actually are outside of requested range .