Count Smaller BIT Solution

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

    n = sorted_nums.length
    tree = array of size (n + 1), filled with 0
    result = empty list

    function query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s

    function update(i):
        while i <= n:
            tree[i] += 1
            i += i & (-i)

    for num in nums from right to left:
        r = rank[num]
        result.append(query(r - 1))
        update(r)

    return result reversed

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

Compare this to the segment tree solution. BIT is noticeably simpler.