Menghitung pasangan inversi

Aplikasi klasik divide and conquer adalah untuk memecahkan masalah berikut:

Diberikan array dari elemen yang berbeda dan dapat dibandingkan, hitung jumlah pasangan inversi dalam array: pasangan sedemikian rupa sehingga dan .( i , j ) a [ i ] > a [ j ] i < $a[1\dots n]$$(i,j)$$a[i] \gt a[j]$$i \lt j$

Salah satu pendekatan untuk ini adalah melakukan Sortir Gabung, tetapi juga menghitung jumlah pasangan inversi dalam sub-masalah. Selama langkah penggabungan, kami menghitung jumlah pasangan inversi yang membentang di (dua) sub-masalah dan menambah jumlah sub-masalah.

Meskipun ini bagus, dan memberikan algoritma waktu , ini mengacaukan array.$O(n\log n)$

Jika kita memiliki batasan tambahan bahwa array adalah read-only, maka kita dapat membuat salinan dan menangani salinan tersebut, atau menggunakan struktur data tambahan seperti statistik urutan pohon biner seimbang untuk melakukan penghitungan, keduanya menggunakan ruang.$\Theta(n)$

Pertanyaan saat ini adalah mencoba dan memperbaiki ruang, sementara tidak mempengaruhi waktu berjalan. yaitu

Apakah ada algoritma waktu untuk menghitung jumlah pasangan inversi, yang bekerja pada array read-only dan menggunakan ruang sub-linear (yaitu )?o ( n $O(n\log n)$$o(n)$

Asumsikan model RAM biaya seragam dan bahwa elemen mengambil ruang dan perbandingan di antara mereka adalah .O ( 1 $O(1)$$O(1)$

Referensi akan dilakukan, tetapi penjelasannya akan lebih baik :-)

Saya mencoba mencari di web, tetapi tidak menemukan jawaban positif / negatif untuk ini. Saya kira ini hanya rasa ingin tahu.

Inilah jawaban Raphael:

Chan dan Pătraşcu memberikan algoritma waktu , tetapi sejauh yang saya tahu dari membaca sepintas lalu, mereka membutuhkan Ω ( n ) ruang. Selanjutnya, Ajtai dkk. membuktikan bahwa setiap (tepat) O ( n ) algoritma streaming waktu membutuhkan Ω ( n ) ruang. Namun, tampaknya ada perkiraan yang cocok dengan kriteria Anda.$o(n\log n)$$\Omega(n)$$O(n)$$\Omega(n)$