Datenstruktur eine Subarray in log (n) zum Invertieren

Question

eine Datenstruktur aufzubauen, die Funktionen hat:

set(arr,n) - Initialisieren der Struktur mit arr Array der Länge n. Zeit O(n)

fetch(i) - holen arr[i]. Zeit O(log(n))

invert(k,j) - (wenn 0 <= k <= j <= n) invertiert das Teilarray [k,j]. Bedeutung [4,7,2,8,5,4] mit invert(2,5) wird [4,7,4,5,8,2]. Zeit O(log(n))

Wie wäre es mit dem Speichern der Indizes im binären Suchbaum und mit einem Flag, dass der Index invertiert ist? Aber wenn ich mehr als 1 invertiere, versaut es es.

Answer 1

So können wir den Entwurf einer solchen Datenstruktur angehen. In der Tat, eine ausgeglichene binäre Suche Baum ist eine gute Idee zu starten.

Lassen Sie uns zunächst Array-Elemente als Paare (index, value). Natürlich sind die Elemente nach Index sortiert, so dass die Intra-order-Traversierung eines Baumes das Array in seiner ursprünglichen Reihenfolge ergibt.

Wenn wir jetzt einen ausgeglichenen binären Suchbaum pflegen und die Größe des Unterbaums in jedem Knoten speichern, können wir bereits in O(log n) holen.

Als nächstes, lassen Sie uns nur so tun, wir speichern den Index. Stattdessen ordnen wir Elemente wie bei (index, value) Paaren an, speichern aber nur den Wert. Die index wird jetzt implizit gespeichert und kann wie folgt berechnet werden. Beginnen Sie mit der Wurzel und gehen Sie zum Zielknoten. Immer, wenn wir in einen linken Teilbaum wechseln, ändert sich die index nicht. Wenn Sie zu einem rechten Teilbaum wechseln, fügen Sie die Größe des linken Teilbaums plus eins (die Größe des aktuellen Eckpunkts) zu index hinzu.

Was wir an diesem Punkt haben, ist ein Array fester Länge in einem ausgewogenen binären Suchbaum gespeichert. Es braucht O(log n), um auf irgendein Element zuzugreifen (zu schreiben oder zu schreiben), im Gegensatz zu O(1) für ein einfaches Array fester Länge, so dass es an der Zeit ist, etwas Nutzen für alle Probleme zu bekommen.

Der nächste Schritt ist es, einen Weg zu aufgeteilt unserer Array in linke und rechte Teile in O(log n) die erforderliche Größe des linken Teils gegeben ersinnen, und fusionieren zwei Arrays durch Verkettung. Dieser Schritt führt die Abhängigkeit von unserer Wahl des ausgewogenen binären Suchbaums ein. Treap ist der offensichtliche Kandidat, da es auf Teilen und primitiven Serien gebaut wird, so dass diese Verbesserung kostenlos kommt. Vielleicht ist es auch möglich, eine Red-black tree oder eine Splay tree in O(log n) zu teilen (obwohl ich zugeben, dass ich nicht versucht habe, die Details selbst herauszufinden).

Momentan ist die Struktur bereits leistungsfähiger als ein Array: Sie erlaubt das Aufteilen und Verketten von "Arrays" in O(log n), obwohl der Zugriff auf Elemente genauso langsam ist wie O(log n). Beachten Sie, dass dies nicht möglich wäre, wenn wir noch index explizit an diesem Punkt gespeichert, da Indizes im rechten Teil einer Teilen oder Merge Operation gespeichert werden würde.

Schließlich ist es Zeit, die Invert Operation einzuführen. Lassen Sie uns in jedem Knoten ein Flag speichern, um zu signalisieren, ob der gesamte Teilbaum dieses Knotens invertiert werden muss. Dieses Flag wird träge propagieren: immer wir einen Knoten zugreifen, bevor Sie etwas tun, überprüfen Sie, ob das Flag true ist. Wenn dies der Fall ist, tauschen Sie die linken und rechten Teilbäume, toggle (true <-> false) das Flag in den Stammknoten der beiden Unterbäume, und setzen Sie das Flag im aktuellen Knoten auf false.

Nun, wenn wir wollen einen Sub-Array invertieren:

• spaltete die Anordnung in drei Teile (vor dem Sub-Array, den Sub-Array selbst, und nach der Sub-Array) von zwei aufgeteilt Operationen,
• Toggle (true <-> false) die Flagge in der Wurzel des mittleren (Subarray) Teils,
• dann die drei Teile wieder in ihrer ursprünglichen Reihenfolge Operationen durch zwei merge verschmelzen.