Liczenie par inwersji

Klasyczne zastosowanie dzielenia i podbijania polega na rozwiązaniu następującego problemu:

Biorąc pod uwagę tablicę różnych, porównywalnych elementów, policz liczbę par inwersji w tablicy: pary ( i , j ) takie, że a [ i ] > a [ j ] i i < j .$a[1\dots n]$$(i,j)$$a[i] \gt a[j]$$i \lt j$

Jednym z podejść jest wykonanie sortowania scalającego, ale także zliczanie liczby par inwersji w pod-problemach. Podczas kroku scalania zliczamy liczbę par inwersji obejmujących (dwa) podproblemy i dodajemy do podproblemów.

Chociaż jest to dobre i daje algorytm czasowy , to miesza tablicę.$O(n\log n)$

Jeśli mamy dodatkowe ograniczenie polegające na tym, że tablica jest tylko do odczytu, możemy wykonać kopię i poradzić sobie z kopią lub użyć dodatkowej struktury danych, takiej jak drzewo binarne zrównoważone statystyki zamówień, aby wykonać zliczanie, z których oba używają spacja.$\Theta(n)$

Bieżącym pytaniem jest próba ulepszenia przestrzeni, bez wpływu na czas działania. to znaczy

Czy istnieje algorytm czasowy do zliczania par par inwersji, który działa na tablicy tylko do odczytu i wykorzystuje przestrzeń subliniową (tj. O ( n ) )?$O(n\log n)$$o(n)$

Załóżmy, że model RAM o jednolitym koszcie i że elementy zajmują miejsce a porównanie między nimi wynosi O ( 1 ) .$O(1)$$O(1)$

Odniesienie się sprawdzi, ale wyjaśnienie będzie lepsze :-)

Próbowałem przeszukać sieć, ale nie znalazłem na to żadnej pozytywnej / negatywnej odpowiedzi. Przypuszczam, że to tylko ciekawostka.

Oto odpowiedź Raphaela:

$o(n\log n)$$\Omega(n)$$O(n)$$\Omega(n)$