Datenstruktur für Intervallaktualisierungen und Abfrage der Anzahl der Nullen

13

Ich suche nach einer Datenstruktur, die eine Ganzzahltabelle der Größe aufrechterhält und die folgenden Operationen in der Zeit .n O ( log n )tnO(logn)

  • increase(a,b) , was erhöht .t[a],t[a+1],,t[b]
  • decrease(a,b) , wodurch t [a], t [a + 1], \ ldots, t [b] verringert werden t[a],t[a+1],,t[b].
  • support() , das die Anzahl der Indizes i zurückgibt, isodass t[i]0 .

Sie haben das Versprechen, dass jeder zu verringernde Anruf mit den gleichen Parametern a, b mit einem vorherigen Anruf abgeglichen werden kann, um zu erhöhen a,b. Die Anwendung, an die ich denke, ist ein Sweepline-Algorithmus, der in der Zeit O(nlogn) die Fläche der Vereinigung von n gegebenen geradlinigen Rechtecken berechnet .

Ein Quad-Baum hätte die Größe , ist also keine Lösung. Fenwick- oder Intervallbäume haben den richtigen Geschmack, aber ich kann sie nicht erweitern, um die obigen Operationen zu unterstützen.Θ(n2)

Christoph Dürr
quelle
Fenwick-Bäume würden nicht das Versprechen verwenden, dass "jeder Anruf zum Verringern mit den gleichen Parametern a, b an einen vorherigen Anruf zum Erhöhen angepasst werden kann", so dass es möglicherweise eine einfachere Lösung gibt, die dieses Versprechen verwendet (aber es entgeht mir vorerst).
Jeremy
Da die Anzahl der möglichen Eingaben höchstens beträgt (Sie können Wiederholungen erkennen und nicht in die Datenstruktur einfügen), erhalten wir immer noch die O ( log n ) -Leistung unter Verwendung der Datenstruktur des gemeinsamen Messbaums. Siehe cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… Folie 47-52. n2O(logn)
Chao Xu
Jérémie und Chao Xu. Vielen Dank für Ihre Kommentare. Ich verstehe jetzt, wie der Intervallbaum verwendet werden kann, um die Gesamtlänge der Vereinigung eines sich ändernden Satzes von Intervallen aufrechtzuerhalten. Dies ist in der Tat eine sehr niedliche Datenstruktur.
Christoph Dürr
Für das allgemeine Datenstrukturproblem erfordert die Suche in Zeit den Raum O ( p ) O ( n 2 ), wobei p die Größe der Liste aktiver Koordinatenpaare ist. Tatsächlich bleibt der Raum für den Sweepline-Algorithmus p O ( n ) also linear. Das Problem ist immer noch offen für eine Datenstruktur mit besserem Platz als O ( p ) , wenn plog(n2)O(log(n))O(p)O(n2)ppO(n)O(p) . pω(n)
Jeremy
2
Hier ist ein netter Link, über den Sie Ihre Implementierungen mit anderen Lösungen für dasselbe Problem vergleichen können: spoj.com/OI/problems/NKMARS
Erel Segal-Halevi

Antworten:

2

Verwenden Sie einen Segmentbaum - eine rekursive Aufteilung des Bereichs in kleinere Bereiche. Jedes Intervall [ a , b ] Ihrer Aktualisierungsvorgänge kann in O ( log n ) der Bereiche in dieser rekursiven Partition unterteilt werden. Für jeden Bereich [ x , y ] speichern Sie:[1,n][a,b]O(logn)[x,y]

  • Die Anzahl der Intervalle [ a , b ] , die vergrößert und nicht verkleinert wurden, so dass [ x , y ] einer der Bereiche ist, in die [ a , b ] unterteilt istc(x,y)[a,b][x,y][a,b]
  • Die Anzahl von Zellen, die nicht durch partitionierte Teilmengen von Intervallen abgedeckt sind , die in der Rekursion bei [ x , y ] oder darunter liegenu(x,y)[x,y]

Wenn dann rekursiv in [ x , z ] und [ z + 1 , w ] aufgeteilt wird , ist u ( x , y ) = { 0, wenn  c ( x , y ) > 0 u ( x , z ) + u ( z + 1 , y ) ansonsten[x,y][x,z][z+1,w]

u(x,y)={0if c(x,y)>0u(x,z)+u(z+1,y)otherwise
So können wir jeden -Wert in konstanter Zeit aktualisieren , wenn sich die anderen Daten für einen Bereich ändern. Jede Supportanfrage kann mit u ( 1 , n ) beantwortet werden .u(x,y)u(1,n)

Um eine Erhöhungsoperation durchzuführen, partitionieren Sie [ a , b ] in O ( log n ) -Bereiche, inkrementieren Sie c ( x , y ) für jeden dieser Bereiche und verwenden Sie die obige Formel, um u ( x , y) neu zu berechnen ) für jeden dieser Bereiche und für jeden ihrer Vorfahren. Die Verkleinerungsoperation ist dieselbe mit einer Verringerung anstelle einer Erhöhung.(a,b)[a,b]O(logn)c(x,y)u(x,y)

David Eppstein
quelle
[x,y][x,y][x,y]u(x,y)=0
[x,y][x,y][x,y]
Könnten Sie ein Beispiel geben?
jbapple
Angenommen, Ihr Intervall ist die Zahl [1,8]. Es wird rekursiv in [1,4], [4,8], dann [1,2], [3,4], [5,6] und [7,8] unterteilt, dann alle Ein-Element-Bereiche. Am Anfang ist alles aufgedeckt, alle c [x, y] = 0 und jeder Bereich hat u = seine Länge. Angenommen, Sie führen eine Operation zum Erhöhen [2,6] durch. Die maximalen O (log n) -Bereiche, in die [2,6] zerlegt werden können, sind [2,2], [3,4] und [5,6], daher setzen wir c [x, y] für diese drei reicht bis 1. Entsprechend der Formel in meiner Antwort bewirkt dies, dass u [x, y] für diese drei Bereiche ebenfalls 0 wird. u [1,2] wird 1, u [1,4] wird ebenfalls 1, u [ 5,8] = 2 und u [1,8] = 1 + 2 = 3
David Eppstein