Подсчет пар инверсии

Классическое приложение «разделяй и властвуй» заключается в решении следующей проблемы:

Учитывая массив различных сопоставимых элементов, подсчитайте количество пар инверсии в массиве: пар ( i , j ), таких что a [ i ] > a [ j ] и i < j .$a[1\dots n]$$(i,j)$$a[i] \gt a[j]$$i \lt j$

Один из подходов к этому - выполнить сортировку слиянием, а также подсчитать количество пар инверсии в подзадачах. На этапе объединения мы подсчитываем количество пар инверсии, которые охватывают (две) подзадачи, и добавляем к подсчетам подзадач.

Хотя это хорошо и дает алгоритм времени , это портит массив.$O(n\log n)$

Если у нас есть дополнительное ограничение, что массив доступен только для чтения, то мы можем сделать копию и обработать копию, или использовать дополнительную структуру данных, такую ​​как сбалансированное двоичное дерево статистики порядка, для подсчета, оба из которых используют пространство.$\Theta(n)$

Текущий вопрос состоит в том, чтобы попытаться улучшить пространство, не влияя на время выполнения. т.е.

Существует ли алгоритм времени для подсчета количества пар инверсии, который работает в массиве только для чтения и использует сублинейное (т. Е. O ( n ) ) пространство?$O(n\log n)$$o(n)$

Предположим, что модель ОЗУ с одинаковой стоимостью и что элементы занимают пространство и сравнение между ними равно O ( 1 ) .$O(1)$$O(1)$

Ссылка подойдет, но объяснение будет лучше :-)

Я пытался найти в Интернете, но не смог найти положительного / отрицательного ответа на этот вопрос. Я полагаю, это просто любопытство.

Вот ответ Рафаэля:

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