Conteggio di inversioni utilizzando BIT

Question

So che questa domanda è stata discussa in precedenza, ma sono interessato a farlo utilizzando un albero indicizzato binario. Ho trovato il link this per mostrare come farlo. Non ho seguito abbastanza la spiegazione. Qualcuno potrebbe darmi una spiegazione del perché il seguente dato è vero.

Create a BIT of size greater than n(no of elements). Iterate through array A (
let j be the index of loop),and for each element A[j] do: 

1) Add j-sum(A[j]) to the number of inversions 
2) add(A[j], 1) (i.e. add 1 to the position A[j] on BIT. This effectively 
counts the number of time value A[j] is seen so far) 

Non capisco perché funzioni.

Answer 1

Un'inversione si verifica quando un elemento è più grande di un elemento che lo segue nell'array.

Possiamo contare le inversioni raggruppandole per il secondo elemento. Ad esempio, nell'array [4, 3, 1, 2], le coppie di elementi (4, 3), (4, 1), (4, 2), (3, 1) e (3, 2) sono inversioni. Li raggruppiamo per secondo elemento, quindi: [[(4, 1), (3, 1)], [(4, 2), (3, 2)], [(4, 3)]].

Consideriamo ogni elemento a turno e contiamo quante inversioni è il secondo elemento di. Nell'esempio, l'elemento 4 è il secondo elemento in 0 inversioni, l'inversione dell'elemento 3 in 1 e gli elementi 1 e 2 in 2 inversioni ciascuno.

Affinché ogni elemento dato sia il secondo elemento di un'inversione, deve esserci un elemento più grande da qualche parte prima di esso nell'array.

Eseguiamo il conteggio in modo efficiente spostando l'array da sinistra a destra e tenendo sempre traccia di quanti elementi di ciascun valore sono stati rilevati finora, utilizzando un BIT. Inizialmente la nostra tabella delle frequenze sarà [0, 0, 0, 0], poiché non abbiamo visto alcun elemento. Dopo aver visitato il 4, aggiorniamo la sua frequenza, dando [0, 0, 0, 1]. Dopo aver visitato il 3, [0, 0, 1, 1] e così via.

Ogni volta che visitiamo una posizione, usiamo il BIT per scoprire quanti elementi visitati finora sono più grandi di esso. Quindi, per esempio, quando incontriamo il 1, il bit contiene attualmente [0, 0, 1, 1], che rappresentano che c'erano finora zero 1 e 2, uno 3 e uno 4. Aggiungendo i valori 0 + 1 + 1 , contiamo il numero di elementi finora superiori a 1.

L'aggiunta di a tutti i questi conteggi individuali indica il numero totale di inversioni.

Si noti che, in generale, è necessario utilizzare la compressione delle coordinate affinché sia ​​efficiente. Ad esempio, se il tuo array iniziale contiene numeri come A = [92, 631, 50, 7], non devi assegnare un BIT con centinaia di elementi. Invece, ordina la matrice per determinare che 7 631, che ci permette di assegnare i ranghi 7 => 1, 50 => 2, 92 => 3, 631 => 4; quindi sostituisci ciascun elemento in base al suo rango, dando B = [3, 4, 2, 1]. Il numero di inversioni di questo array sarà lo stesso dell'originale, poiché B [i]> B [j] se e solo se A [i]> A [j].

(Nota: un vero programmatore probabilmente userebbe indici partendo da zero)