Zliczanie inwersji za pomocą BIT

Question

Wiem, że to pytanie zostało omówione wcześniej, ale jestem zainteresowany robieniem tego przy użyciu drzewa indeksowanego binarnie. Znalazłem link this, aby pokazać, jak to zrobić. Nie bardzo podążałem za wyjaśnieniem. Czy ktoś mógłby podać mi wyjaśnienie, dlaczego podane poniżej są prawdziwe.

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) 

Nie rozumiem, dlaczego to działa.

Answer 1

Odwrócenie następuje, gdy element jest większe niż pewne elementy, które po nim w tablicy.

Możemy liczyć inwersje, grupując je według drugiego elementu. Na przykład w macierzy [4, 3, 1, 2] pary elementów (4, 3), (4, 1), (4, 2), (3, 1) i (3, 2) są inwersje. Grupujemy je według drugiego elementu, stąd: [[(4, 1), (3, 1)], [(4, 2), (3, 2)], [(4, 3)]].

Uważamy każdy element po kolei, a ilu inwersji jest drugim elementem. W przykładzie element 4 jest drugim elementem w 0 odwróceniu, inwersji elementu 3 w 1 oraz elementach 1 i 2 w 2 odwróceniach.

Aby każdy dany element jest drugi element inwersji, musi być większy elementu gdzie przed nią w układzie.

Wykonujemy liczbę efektywnie przez przejeżdżające tablicę od lewej do prawej i zawsze śledzenie jak wiele elementów każdej wartości zostały napotkane dotąd, używając nieco. Początkowo nasza tabela częstotliwości będzie [0, 0, 0, 0], ponieważ nie widzimy żadnych elementów. Po odwiedzeniu 4, aktualizujemy jego częstotliwość, podając [0, 0, 0, 1]. Po przejściu do 3, [0, 0, 1, 1] i tak dalej.

każdym razem odwiedzamy miejsce, używamy BIT, aby dowiedzieć się, jak wiele elementów odwiedził do tej pory są większe niż to. Tak więc na przykład, gdy napotkamy 1, BIT zawiera obecnie [0, 0, 1, 1], co oznacza, że ​​były do ​​tej pory zero 1 i 2, jeden 3 i jeden 4. Dodając wartości 0 + 1 + 1 liczymy liczbę elementów tak daleko, że są większe niż 1.

Dodawanie wszystkie te indywidualne liczy daje łączną liczbę inwersji.

Należy pamiętać, że aby wydajność była skuteczna, należy zastosować kompresję współrzędnych . Na przykład, jeśli twoja początkowa tablica zawiera liczby takie jak A = [92, 631, 50, 7], nie powinieneś przydzielać BIT z setkami elementów. Zamiast tego posortuj tablicę, aby określić, że50 631, która pozwala nam przypisać szeregi 7 => 1, 50 => 2, 92 => 3, 631 => 4; następnie zamień każdy element na jego pozycję, dając B = [3, 4, 2, 1]. Liczba inwersji tej tablicy będzie taka sama jak w oryginale, ponieważ B [i]> B [j] if i only if A [i]> A [j].

(Uwaga: prawdziwy programista prawdopodobnie używałby wskaźników zaczynających się od zera.)