Ich suche nach einer Datenstruktur, die eine Ganzzahltabelle der Größe aufrechterhält und die folgenden Operationen in der Zeit .n O ( log n )
- , was erhöht .
- , wodurch t [a], t [a + 1], \ ldots, t [b] verringert werden .
- , das die Anzahl der Indizes i zurückgibt, sodass .
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 . Die Anwendung, an die ich denke, ist ein Sweepline-Algorithmus, der in der Zeit 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.
ds.data-structures
cg.comp-geom
Christoph Dürr
quelle
quelle
Antworten:
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]
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]
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)
quelle
quelle