Intervallo query il numero di inversione di O (lg N)

Question

Dato un array non ordinato di n numeri interi, so di poter trovare il numero totale di inversioni che utilizzano BIT a O (N lg N) seguendo questo metodo: Count Inversion by BIT

Tuttavia è possibile se devo interrogare un intervallo arbitrario per il numero totale di inversioni in O (lg N)?

È possibile pre-computazione A O (N lg N).

Ho fatto qualche ricerca e sembra che il fattore N non sia evitabile ... Qualche suggerimento sarebbe apprezzato!

Answer 1

Questa non è la risposta per la quale stai cercando, ma ho due suggerimenti.

Innanzitutto, non penso che BIT sia la struttura dati corretta da utilizzare per il problema che si sta tentando di risolvere. Il vantaggio di BIT è che mantiene una somma di prefisso interrogabile O (lg n) usando solo O (lg n) per inserimento. Poiché non si sta inserendo una volta completata la struttura dei dati, BIT non è vantaggioso (perché è possibile utilizzare un semplice array di prefissi di prefix, che è interrogabile in O (1)).

In secondo luogo, ho un algoritmo ingenuo che utilizza O (n) il tempo e lo spazio per costruire una struttura di dati che può trovare inversioni media a O (1) tempo:

In primo luogo, costruire una (n X n) matrice di mappatura delle inversioni, in modo che mat[i][j]=1 solo se i<j e arr[i] e arr[j] sono invertiti. Quindi, calcola una somma di prefisso su ogni riga di questa matrice, in modo che mat[i][j] sia il numero di inversioni che includono arr[i] nell'intervallo [i,j]. Infine, calcola una somma suffisso su ogni colonna, in modo che sia il numero totale di inversioni nell'intervallo [i,j].

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]; 

Questo caratterizza O (n) tempo e spazio, ma il numero di inversioni in qualsiasi intervallo possono essere interrogati in tempo costante.