Count Smaller Solution

The BIT approach is recommended for this problem:

function countSmaller(nums)
    // Coordinate compress
    sorted := sort(unique(nums))
    rank := map value to index

    result := []
    bit := BIT of size len(sorted)

    for i from n - 1 down to 0
        r := rank[nums[i]]
        result.append(bit.query(r - 1))
        bit.update(r, 1)

    return reverse(result)

Process right to left. Query counts smaller (indices 0 to r-1), then mark current value.

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