Contando pares de inversión

Una aplicación clásica de divide y vencerás es resolver el siguiente problema:

Dada una matriz de elementos distintos y comparables, cuente el número de pares de inversión en la matriz: pares modo que e .( i , j ) a [ i ] > a [ j ] i < $a[1\dots n]$$(i,j)$$a[i] \gt a[j]$$i \lt j$

Un enfoque para esto es hacer una Clasificación de fusión, pero también contar el número de pares de inversión en los subproblemas. Durante el paso de fusión, contamos el número de pares de inversión que abarcan los (dos) subproblemas y los sumamos a los recuentos de los subproblemas.

Si bien esto es bueno y proporciona un algoritmo de tiempo , esto confunde la matriz.$O(n\log n)$

Si tenemos la restricción adicional de que la matriz es de solo lectura, entonces podemos hacer una copia y manejar la copia, o usar una estructura de datos adicional como un árbol binario equilibrado de estadísticas de orden para hacer el recuento, los cuales usan espacio.$\Theta(n)$

La pregunta actual es intentar mejorar el espacio, sin afectar el tiempo de ejecución. es decir

¿Existe un algoritmo de tiempo para contar el número de pares de inversión, que funciona en una matriz de solo lectura y usa espacio sub-lineal (es decir, )?o ( n $O(n\log n)$$o(n)$

Suponga un modelo RAM de costo uniforme y que los elementos ocupan espacio y la comparación entre ellos es .O ( 1 $O(1)$$O(1)$

Una referencia servirá, pero una explicación será mejor :-)

Intenté buscar en la web, pero no pude encontrar ninguna respuesta positiva / negativa para esto. Supongo que esto es solo una curiosidad.

Aquí está la respuesta de Raphael:

Chan y Pătraşcu dan un algoritmo de tiempo , pero, por lo que puedo deducir del descremado, necesitan espacio Ω ( n ) . Además, Ajtai et al. demuestre que cualquier algoritmo de transmisión de tiempo O ( n ) (exacto) necesita espacio Ω ( n ) . Sin embargo, parece haber aproximaciones que se ajustan a sus criterios.$o(n\log n)$$\Omega(n)$$O(n)$$\Omega(n)$