Bereich Abfrage der Anzahl der Inversion in O (lg N)

Question

eine unsortierte Array von n ganzen Zahlen gegeben, ich weiß, dass ich die Gesamtzahl von Umkehrungen findet BIT in O (N lg N) nach dieser Methode: Count Inversion by BIT

Aber ist es möglich, wenn ich einen willkürlichen Bereich für die Gesamtzahl der Inversionen in O (lg N) abfragen muss?

Eine O (N lg N) Vorberechnung ist akzeptabel.

Ich habe einige Nachforschungen gemacht und scheint der N-Faktor ist nicht vermeidbar ... Alle Vorschläge wären willkommen!

Answer 1

Dies ist nicht die Antwort, für die Sie suchen, aber ich habe zwei Vorschläge.

Erstens glaube ich nicht, dass BIT die richtige Datenstruktur für das Problem ist, das Sie versuchen zu lösen. Der Vorteil von BIT besteht darin, dass es eine abfragbare 0 (lg n) -Präfix-Summe unter Verwendung von nur O (lg n) pro Einfügung beibehält. Da Sie nicht einfügen, sobald Ihre Datenstruktur abgeschlossen ist, ist BIT nicht vorteilhaft (weil Sie ein einfaches Präfix-Summen-Array verwenden könnten, das in O (1) abfragbar ist).

Zweitens Ich habe einen naiven Algorithmus, O (n) Zeit und Raum verwendet eine Datenstruktur zu konstruieren, die Bereich Inversionen in O (1) Zeit finden:

Zuerst Konstrukt eines (n X n) Matrix-Mapping der Inversionen, so dass mat[i][j]=1 nur wenn i<j und arr[i] und arr[j] invertiert sind. Berechnen Sie dann eine Präfixsumme über jede Zeile dieser Matrix, so dass mat[i][j] die Anzahl der Inversionen ist, die arr[i] im Bereich [i,j] beinhalten. Berechnen Sie schließlich eine Suffixsumme für jede Spalte, sodass mat[i][j] die Gesamtanzahl der Inversionen im Bereich [i,j] ist.

for i from 0 to n-2 
    for j from i+1 to n-1 
    if(arr[j] > arr[i]) 
     mat[i][j] = 1; 
for i from 0 to n-2 
    for j from i+1 to n-1 
    mat[i][j] += mat[i][j-1]; 
for j from n-1 to 1 
    for i from j-1 to 0 
    mat[i][j] += mat[i+1][j]; 

Dies nimmt deutlich O (n 2 ) Zeit und Raum, aber die Anzahl von Umkehrungen in jedem Bereich kann in konstanter Zeit abgefragt wird.