Ich denke, der einfachste Weg, um alle gewünschten Funktionen mit O (log N) -Zeitkomplexität zu implementieren und gleichzeitig die Speicheranforderungen zu minimieren, ist die Verwendung eines Bitvektors zum Speichern aller 0/1 (freie / verwendete) Werte. Bit-Vektor kann 6 niedrigste Ebenen sowohl des Fenwick-Baums als auch des Segment-Baums ersetzen (wenn sie als 64-Bit-Ganzzahlen implementiert sind). So kann die Höhe dieser Bäume um 6 reduziert werden und der Platzbedarf für jeden dieser Bäume wäre 64 (oder 32) mal geringer als üblich.

Der Segmentbaum kann als impliziter Binärbaum implementiert werden, der in einem Array sitzt (genau wie eine bekannte Max-Heap-Implementierung). Wurzelknoten bei Index 1, jeder linke Nachkomme des Knotens bei Index i wird bei 2*i platziert, jeder rechte Nachkomme - bei 2*i+1 . Das bedeutet, dass im Vergleich zum Fenwick-Baum doppelt so viel Platz benötigt wird, aber da die Baumhöhe um 6 Stufen reduziert ist, ist das kein großes Problem.

Jeder Segmentbaumknoten sollte einen einzelnen Wert speichern - Länge der längsten zusammenhängenden Folge von "freien" Slots beginnend an einem von diesem Knoten abgedeckten Punkt (oder Null, wenn kein solcher Startpunkt vorhanden ist). Dies macht die Suche nach dem ersten Bereich einer gegebenen Anzahl von zusammenhängenden Nullen sehr einfach: Beginnen Sie bei der Wurzel und wählen Sie dann den linken Nachkomme, wenn er einen Wert größer oder gleich als erforderlich enthält, andernfalls wählen Sie den rechten Nachkomme. Nachdem Sie zu einem Blattknoten gelangt sind, prüfen Sie das entsprechende Wort des Bitvektors (für eine Folge von Nullen in der Mitte des Wortes).

Aktualisierungsvorgänge sind komplizierter. Wenn Sie einen Wert auf "used" ändern, prüfen Sie das entsprechende Wort des Bitvektors, wenn es leer ist, segmentieren Sie den Segmentbaum, um einen Wert ungleich Null für einen linken Nachkommen zu finden, und dann den Baum, um mit diesem Wert zum ganz rechten Blatt zu gelangen hinzugefügter Slot teilt "freies" Intervall in zwei Hälften auf, aktualisiert dann alle übergeordneten Knoten sowohl für den hinzugefügten Slot als auch den Startknoten des zu spaltenden Intervalls und setzt auch ein Bit in den Bitvektor. Das Ändern eines Wertes in "frei" kann ähnlich implementiert werden.

Wenn auch die Anzahl von Elementen ungleich Null in einem bestimmten Bereich benötigt wird, implementieren Sie den Fenwick-Baum über denselben Bitvektor (aber getrennt vom Segmentbaum). Es gibt nichts Besonderes in der Implementierung des Fenwick-Baums, außer dass das Addieren von 6 niedrigsten Knoten durch die Operation "Populationszählung" für irgendein Wort des Bitvektors ersetzt wird. Für ein Beispiel der Verwendung von Fenwick-Baum zusammen mit Bit-Vektor siehe erste Lösung für Magic Board auf CodeChef.

Alle notwendigen Operationen für den Bitvektor können mit verschiedenen bitweisen Tricks ziemlich effizient implementiert werden. Für einige von ihnen (führende / nachfolgende Nullzählung und Populationszählung) können Sie entweder Compiler-Intrinsics oder Assembler-Anweisungen verwenden (abhängig von der Zielarchitektur).

Wenn der Bitvektor mit 64-Bit-Wörtern und Baumknoten implementiert wird - mit 32-Bit-Worten belegen beide Bäume zusätzlich zum Bitvektor 150% Platz. Dies kann signifikant reduziert werden, wenn jeder Blattknoten nicht einem einzelnen Bitvektorwort entspricht, sondern einem kleinen Bereich (4 oder 8 Wörter). Für 8 Wörter würde zusätzlicher Platzbedarf für Bäume nur 20% der Bitvektorgröße betragen. Dies macht die Implementierung etwas komplizierter. Wenn sie richtig optimiert ist, sollte die Leistung ungefähr gleich sein wie in der Variante für ein Wort pro Blattknoten. Bei sehr großen Datenmengen ist die Leistung wahrscheinlich besser (weil Bitvektorberechnungen cachefreundlicher sind als das Blättern der Bäume).

Wie mcdowella in ihre Antwort vorschlägt, sei K2 = K / 2, rundet sich auf, und M sei der kleinste Potenz von 2, das ist & gt; = K2. Ein vielversprechender Ansatz wäre, nach zusammenhängenden Blöcken von K2-Nullen zu suchen, die vollständig in einem Block der Größe M enthalten sind, und wenn wir diese gefunden haben, überprüfen wir Blöcke der benachbarten Größe M, um zu sehen, ob sie genügend benachbarte Nullen enthalten. Wenn für den ersten Scan die Anzahl der Nullen in einem Block & lt; K2, klar können wir es überspringen, und wenn die Anzahl der 0s & gt; = K2 ist und die Größe des Blocks & gt; = 2 · M ist, können wir beide Unterblöcke betrachten.

Dies schlägt den folgenden Code vor. Unten ist A [0 .. N-1] das Fenwick-Baum-Array; Es wird angenommen, dass N eine Potenz von 2 ist. Ich gehe davon aus, dass Sie leere Slots zählen und nicht leere. Wenn Sie es vorziehen, leere Slots zu zählen, ist es einfach, von einem zum anderen zu wechseln.

Damit können wir alle Blöcke der Größe M mit mindestens K / 2 Nullen in der Reihenfolge verarbeiten. Sie können die Reihenfolge, in der Sie die erste und die zweite Hälfte auf q schieben, sogar zufallsgenerieren, um die Blöcke in zufälliger Reihenfolge zu erhalten. Dies könnte nützlich sein, um die Situation zu bekämpfen, in der die erste Hälfte Ihres Arrays viel schneller gefüllt wird zweite Hälfte.

Jetzt müssen wir besprechen, wie man einen einzelnen Block bearbeitet. Wenn z = j, dann ist der Block vollständig mit 0 gefüllt und wir können sowohl nach links als auch nach rechts schauen, um Nullen hinzuzufügen. Andernfalls müssen wir herausfinden, ob es mit & gt; = K / 2 zusammenhängenden Nullen beginnt, und wenn ja, mit wie viel genau, und dann prüfen, ob der vorherige Block mit einer geeigneten Anzahl von Nullen endet. In ähnlicher Weise prüfen wir, ob der Block mit & gt; = K / 2 zusammenhängenden Nullen endet, und wenn ja, mit wie viel genau, und dann prüfen, ob der nächste Block mit einer geeigneten Anzahl von Nullen beginnt. Wir brauchen also eine Prozedur, um die Anzahl der Nullen zu finden, mit denen ein Block beginnt oder endet, möglicherweise mit einer Abkürzung, wenn es mindestens a oder höchstens b ist. Um genau zu sein: lasst end_with_zeroes (i, j, min, max) eine Prozedur sein, die die Anzahl der Nullen zurückgibt, die der Block von [i-j + 1 .. j] endet, mit einer Abkürzung, um max zurückzugeben, wenn das Ergebnis wird mehr als max und min sein, wenn das Ergebnis kleiner als min ist. Ähnlich für starts_with_zeroes (i, j, min, max).

Beachten Sie, dass es im zweiten Fall, in dem wir eine Lösung finden, möglich sein könnte, den Startpunkt etwas weiter nach links zu verschieben. Sie können dies separat überprüfen, wenn Sie die allererste Position benötigen, die es starten könnte.

Jetzt müssen nur noch Starts_with_zeroes und ends_with_zeroes implementiert werden. Um zu überprüfen, ob der Block mit mindestens Nullen beginnt, können wir testen, ob er mit 2 ^ h Nullen beginnt (wobei 2 ^ h & lt; = min), indem der entsprechende Fenwick-Eintrag geprüft wird; dann überprüfe auf ähnliche Weise, ob es mit 2 ^ H Nullen beginnt, wo 2 ^ H & gt; = max, um den anderen Weg zu verkürzen (außer wenn max = j, ist es schwieriger, die richtige Zahl vom Fenwick-Baum zu finden); dann finden Sie die genaue Nummer.

Wie Sie sehen, ist starts_with_zeroes ziemlich bottom-up. Für ends_with_zeroes, denke ich, dass du einen Top-Down-Ansatz machen möchtest, da es etwas schwieriger ist, die zweite Hälfte von etwas in einem Fenwick-Baum zu untersuchen. Sie sollten in der Lage sein, eine ähnliche Art von binärer Suche-Stil-Iteration zu machen.

Dieser Algorithmus ist definitiv nicht O (log (N)), und ich habe eine Ahnung, dass dies unvermeidlich ist. Der Fenwick-Baum gibt einfach keine Informationen, die für deine Frage gut sind. Ich denke jedoch, dass dieser Algorithmus in der Praxis ziemlich gut abschneidet, wenn geeignete Intervalle ziemlich üblich sind.

Eine schnelle Überprüfung, wenn nach einem Bereich von K zusammenhängenden Schlitzen gesucht wird, besteht darin, die größte Potenz von zwei kleiner als oder gleich K / 2 zu finden. Irgendwelche K kontinuierlichen Null-Schlitze müssen mindestens einen Fenwick-ausgerichteten Bereich von Schlitzen der Größe & lt; = K / 2 enthalten, der vollständig mit Nullen gefüllt ist. Sie könnten den Fenwick-Baum von oben nach solchen Stücken von ausgerichteten Nullen durchsuchen und dann nach dem ersten suchen, der erweitert werden kann, um einen Bereich von K zusammenhängenden Nullen zu erzeugen.

In Ihrem Beispiel enthält die unterste Ebene 0s oder 1s und die obere Ebene enthält Summen von Nachkommen. Das Auffinden von Nullen ist einfacher, wenn die niedrigste Ebene 0s enthält, wo Sie gerade 1s schreiben, und die Anzahl der zusammenhängenden Nullen auf der linken Seite, wo Sie gerade Nullen schreiben, und die oberen Ebenen den maximalen Wert eines Nachfahrens enthalten. Das Aktualisieren würde mehr Arbeit bedeuten, besonders wenn Sie lange Strings von Nullen erzeugen und zerstören würden, aber Sie könnten die linke Zeichenkette von Nullen mit mindestens K mit einer einzigen Suche links von der Verzweigung finden, wo der maximale Wert mindestens K war Tatsächlich ist hier ein Großteil der Update-Arbeit erledigt, indem man Läufe von 1,2,3,4 ... auf der untersten Ebene erstellt und zerstört. Vielleicht, wenn Sie die niedrigste Ebene wie ursprünglich definiert verlassen und eine Fall-zu-Fall-Analyse der Auswirkungen von Änderungen durchgeführt haben, können Sie die oberen Ebenen die längste Nullenfolge beginnend bei jedem Nachkommen eines bestimmten Knotens - für die schnelle Suche - haben und vernünftig werden Kosten aktualisieren.

@Erik hat einen vernünftig klingenden Algorithmus behandelt. Beachten Sie jedoch, dass dieses Problem im ungünstigsten Fall eine geringere Komplexitätsgrenze von Ω (N / K) aufweist.

Beweis:

Betrachten Sie eine reduzierte Version des Problems, wo:

• N und K sind beide Potenzen von 2
• N & gt; 2K & gt; = 4

Angenommen, Ihr Eingabe-Array besteht aus (N / 2K) Chunks der Größe 2K. Ein Chunk hat die Form K 0s, gefolgt von K 1, jeder zweite Chunk ist die Zeichenkette "10", die K mal wiederholt wird. Es gibt (N / 2K) solche Arrays, jede mit genau einer Lösung für das Problem (der Anfang des einen "speziellen" Chunks).

Sei n = log2 (N), k = log2 (K). Definieren wir auch den Wurzelknoten des Baums auf der Ebene 0 und die Blattknoten auf der Ebene n des Baums.

Beachten Sie, dass die Ebene n-k des Baumes einfach aus der Anzahl von 1en in jedem Chunk besteht, da unser Array aus ausgerichteten Chunks der Größe 2K besteht. Jedoch hat jeder unserer Chunks die gleiche Anzahl von 1s darin. Dies bedeutet, dass jeder Knoten auf der Ebene n-k identisch ist, was wiederum bedeutet, dass jeder Knoten auf der Ebene & lt; = n-k ebenfalls identisch ist.

Was das bedeutet ist, dass der Baum keine Informationen enthält, die den "speziellen" Chunk entzweien können, bis Sie mit der Analyse der Level n-k + 1 und niedriger beginnen. Aber da alle bis auf zwei der (N / K) Knoten auf dieser Ebene identisch sind, bedeutet dies, dass Sie im schlimmsten Fall O (N / K) Knoten untersuchen müssen, um die Lösung vom Rest der Knoten zu unterscheiden Knoten.