Inversions with BIT

Algorithm:

$1.$ Coordinate compress values to range $[1, n]$

$2.$ Process array right to left

$3.$ For each element $x$: query prefix sum up to $x-1$ (count of smaller elements seen)

$4.$ Update position $x$ with $+1$

function countInversions(arr):
    // Coordinate compress
    sorted_arr = sorted unique values of arr
    rank = map each value v to its 1-based position in sorted_arr

    n = sorted_arr.length
    bit = array of size (n + 1), filled with 0
    inversions = 0

    for x in arr from right to left:
        r = rank[x]
        // Count elements smaller than x (already processed = to the right)
        inversions += query(r - 1)
        update(r, 1)

    return inversions

Time: $O(n \log n)$. Space: $O(n)$.