Algorithmus für das Präfixparitätsproblem

Das Präfixparitätsproblem kann wie folgt definiert werden. Sie erhalten eine Zeichenfolge der Länge und anfangs ist jedes Zeichen . Anschließend möchten Sie eine Datenstruktur erstellen, die Aktualisierungen wie die folgenden unterstützt.n $S$$n$$0$

1. Für eine gegebene $i$ ändere ich $S[i]$ entweder auf $0$ oder $1$
2. für eine gegebene finde $i$ die Parität von $S[1]+S[2]+...+S[i]$ .

Aus meiner Sicht gibt es eine Lösung, die diese Art von Abfragen in $O(\log n)$ -Zeit unterstützt, während nur linearer Raum und lineare Vorverarbeitungszeit zum Erstellen der Datenstruktur verwendet werden. Die Idee ist, einen vollständigen binären Suchbaum über der Zeichenfolge zu erstellen, wobei die Blätter einzelnen Zeichen von $S$ In jedem internen Knoten speichern wir die Summe aller Zeichen, die Blätter sind, in dem von diesem Knoten definierten Unterbaum. Auf diese Weise können wir beide Updates trivial in $O(\log n)$ Zeit unterstützen.

Ich habe jedoch ein Papier gefunden, das eine Untergrenze für dieses Problem belegt und besagt, dass Sie es nicht besser machen können als für die Updates, und ich fand auch das folgende Papierhttp://link.springer.com/chapter/10.1007%2F3-540-51542-9_5und einen direktenLink zum PDF, der einen Algorithmus angibt, der dies erreicht gebunden, also optimal.$O(\frac{\log n}{\log \log n})$

Ich würde diesen Algorithmus gerne verstehen, aber die Erklärung ist wie 1 Seite, und viele Details fehlen.

Ich habe mich also gefragt, ob es zu diesem Problem eine andere Quelle gibt, weil ich es sehr schwer finde, eine zu finden, oder ist dies die einzige verfügbare Quelle?

Vielen Dank im Voraus

Ich habe das von Ihnen verlinkte Papier kurz durchgelesen. Basierend auf den in diesem Artikel gegebenen Ideen ist hier eine einfache Datenstruktur, die ein O ( log n) erhältZeitbindung für jede Operation.$O(\frac{\log n}{\log\log n})$

Sie haben in Ihrer Frage erwähnt, dass Sie ausgewogene, erweiterte Bäume verwenden können, um dies zu beschleunigen. Insbesondere wenn Sie einen Binärbaum haben und jeden Knoten mit der Parität seines linken Teilbaums erweitern, können Sie Aktualisierungen und Suchvorgänge jeweils in der Zeit . Das ist schnell, aber nicht schnell genug.$O(\log n)$

Betrachten Sie nun die folgende Verallgemeinerung Ihrer Idee. Angenommen, wir verwenden anstelle eines Binärbaums einen Mehrwegbaum mit dem Verzweigungsfaktor . Wir erweitern jeden Schlüssel in jedem Knoten mit der Parität aller vorhergehenden Teilbäume (dies verallgemeinert die Idee, die Parität des linken Teilbaums zu speichern). Lassen Sie uns nun darüber nachdenken, wie wir in diesem Baum nachschlagen oder aktualisieren würden. Um eine Suche durchzuführen, verwenden wir eine leicht modifizierte Version des binären Baumsuchalgorithmus von zuvor: Gehen Sie von der Oberseite des Baums nach unten, wobei Sie bei jedem Schritt die Parität des Teilbaums rein links von jedem Knoten akkumulieren. Die Höhe des Baumes ist in diesem Fall O ( log k n ) und wir machen O ( 1 $k$$O(\log_k n)$$O(1)$Arbeit pro Knoten, daher betragen die Kosten für die Suche .$O(\log_k n)$

Mit diesem Setup steigen jedoch die Kosten für ein Update. Insbesondere wenn wir die Parität eines Elements ändern, müssen wir vom unteren Rand des Baums nach oben gehen und die gespeicherte Parität jedes Schlüssels in jedem Knoten auf dem Pfad nach oben ändern. Es gibt Schlüssel pro Knoten und O $k$ Knoten auf dem Weg von den Blättern nach oben, sodass die Kosten für die Ausführung einer solchen Operation O ( k log k n ) = O ( k ) $O(\log_k n)$, was zu langsam ist. Wenn wir diesen zusätzlichenk-Begriffirgendwie eliminieren könnten, wären wir im Geschäft.$O(k \log_k n) = O(\frac{k}{\log k} \log n)$$k$

Die Einsicht, die das Papier hat, ist die folgende. Wenn Sie über unser anfängliches Problem nachdenken, hatten wir ein Array der Größe und wollten Präfixparitäten berechnen können. Wir haben jetzt einen k -ary-Baum, in dem wir an jedem Knoten in der Lage sein müssen, das Problem der Präfixparität auf Arrays der Größe k zu lösen , da jeder Knoten Informationen über die darunter liegenden Ebenen zwischenspeichert. In der obigen Datenstruktur haben wir das Problem der Präfixparität an jedem Knoten gelöst, indem wir nur ein Array der Präfixparitäten gespeichert haben. Wenn wir also eine Aktualisierung durchführen müssen, betragen die Kosten O ( k ) . Die Erkenntnis des Papiers ist, dass Sie durch die Verwendung einer clevereren Datenstruktur an jedem Knoten diese Aktualisierungen wesentlich effizienter durchführen können.$n$$k$$k$$O(k)$

Das Papier gibt insbesondere die folgenden Erkenntnisse. Nehmen wir an, dass "klein" ist, für eine Definition von klein, die wir später auswählen werden. Wenn Sie das Präfixparitätsproblem auf einem Array der Größe k lösen möchten , gibt es nur 2 log k n $k$$k$ verschiedene mögliche Bitarrays der Länge k . Darüber hinaus gibt es nur k mögliche Suchabfragen, die Sie für ein Bit-Array der Größe k durchführen können . Infolgedessen beträgt die Anzahl möglicher Kombinationen eines Arrays und einer Abfrage k 2 k . Wenn wir k wählen$2^k$$k$$k$$k$$k 2^k$$k$Um klein genug zu sein, können wir diese Menge so klein machen, dass es möglich wird, das Ergebnis jedes möglichen Arrays und jeder möglichen Abfrage vorab zu berechnen. Wenn wir das tun, können wir unsere Datenstruktur wie folgt aktualisieren. In jedem Knoten des Weg-Baums speichern wir stattdessen ein Array von k Bits, eines für jeden Schlüssel im Knoten , anstatt dass jeder Schlüssel die Parität seines linken Teilbaums speichert . Wenn wir die Parität aller Knoten links vom i- ten Kind ermitteln möchten, suchen wir einfach in einer Tabelle, die durch diese k Bits (als Ganzzahl behandelt) und den Index i indiziert ist . Vorausgesetzt, wir können diese Tabelle schnell genug berechnen, bedeutet dies, dass das Ausführen einer Präfix-Paritätsabfrage noch Zeit O benötigt $k$$k$$i$$k$$i$$O(\log_k n)$ , aber jetzt brauchen Aktualisierungen auch Zeit da die Kosten für eine Präfixparitätsabfrage auf einem bestimmten Knoten O ( 1 ) betragen .$O(\log_k n)$$O(1)$

Die Autoren des Papiers bemerkten, dass wenn Sie k = lg n wählen , dann ist die Anzahl der möglichen Abfragen, die gemacht werden können,lg$k = \frac{\lg n}{2}$. Darüber hinaus betragen die Kosten für die Ausführung einer Operation für den resultierenden BaumO$\frac{\lg n}{2} 2^{\frac{\lg n}{2}} = \frac{\lg n}{2} \sqrt{n} = o(n)$$O(\log_k n) = O(\frac{\log n}{\log \frac{\lg n}{2}}) = O(\frac{\log n}{\log \log n})$ . Der Haken ist, dass Sie jetzt zu Beginn des Einrichtens der Datenstruktur eine -Vorberechnung durchführen müssen. Die Autoren geben eine Möglichkeit, diese Kosten zu amortisieren, indem sie für die ersten Abfragen eine andere Datenstruktur verwenden, bis genügend Arbeit geleistet wurde, um die zum Einrichten der Tabelle erforderliche Arbeit zu rechtfertigen, obwohl Sie argumentieren könnten, dass Sie O ( n) ausgeben müssen ) Zeit, den Baum in erster Linie aufzubauen und dass dies keinen Einfluss auf die Gesamtlaufzeit hat.$o(n)$$O(n)$

Zusammenfassend lautet die Idee also wie folgt:

• Verwenden Sie anstelle eines erweiterten Binärbaums einen erweiterten -ary-Baum.$k$
• $k$$k$
• Verwenden Sie diese vorberechnete Datenstruktur an jedem Knoten im Baum.
• $k = \frac{\lg n}{2}$$O(\frac{\log n}{\log \log n})$
• Vermeiden Sie die Kosten für die Vorberechnung im Voraus, indem Sie in jedem Knoten eine temporäre Ersatzdatenstruktur verwenden, bis sich die Vorberechnung lohnt.

Alles in allem ist es eine clevere Datenstruktur. Vielen Dank, dass Sie diese Frage gestellt und verknüpft haben - ich habe dabei viel gelernt!

$O(\log n)$$O(\frac{\log n}{\log \log n})$