Contando pares de inversão

Uma aplicação clássica de dividir e conquistar é resolver o seguinte problema:

Dada uma matriz de elementos distintos e comparáveis, conte o número de pares de inversão na matriz: pares modo que e .$a[1\dots n]$$(i,j)$$a[i] \gt a[j]$$i \lt j$

Uma abordagem para isso é fazer uma classificação de mesclagem, mas também contar o número de pares de inversão nos subproblemas. Durante a etapa de mesclagem, contamos o número de pares de inversão que se estendem pelos (dois) subproblemas e aumentam as contagens dos subproblemas.

Enquanto isso é bom e fornece um algoritmo de tempo , isso atrapalha a matriz.$O(n\log n)$

Se tivermos a restrição adicional de que a matriz é somente leitura, podemos fazer uma cópia e lidar com a cópia ou usar uma estrutura de dados adicional, como uma árvore binária balanceada de estatísticas de ordem para fazer a contagem, ambas as quais usam $\Theta(n)$ Espaço teta (n) .

A questão atual é tentar melhorar o espaço, sem afetar o tempo de execução. ie

Existe um algoritmo de tempo $O(n\log n)$ para contar o número de pares de inversão, que funciona em uma matriz somente leitura e usa espaço sub-linear (isto é, $o(n)$ )?

Suponha um modelo de RAM de custo uniforme e que os elementos $O(1)$ espaço O (1) e a comparação entre eles seja $O(1)$ .

Uma referência serve, mas uma explicação será melhor :-)

Tentei pesquisar na web, mas não consegui encontrar nenhuma resposta positiva / negativa para isso. Suponho que isso seja apenas uma curiosidade.

Aqui está a resposta de Rafael:

Chan e Pătraşcu fornecem um algoritmo de tempo , mas, tanto quanto posso ver ao escanear o papel, eles precisam de Ω ( n ) espaço. Além disso, Ajtai et al. provar que qualquer algoritmo (exato) de O ( n ) tempo de fluxo precisa de Ω ( n ) espaço. Parece haver aproximações que atendem aos seus critérios.$o(n\log n)$$\Omega(n)$$O(n)$$\Omega(n)$