Count Smaller Solution

Process right to left. For each element:

$1.$ Query: count of elements smaller than current (already in tree)

$2.$ Update: add current element to tree

function countSmaller(nums):
    // Coordinate compression
    sortedNums = sort(unique(nums))
    rank = {}
    for i from 0 to sortedNums.length - 1:
        rank[sortedNums[i]] = i

    n = sortedNums.length
    tree = new SegmentTree(n)
    result = []

    for each num in reverse(nums):
        r = rank[num]
        // Count elements with rank < r
        count = (r > 0) ? tree.query(0, r - 1) : 0
        result.add(count)
        tree.update(r, tree.query(r, r) + 1)

    return reverse(result)

Time: $O(n \log n)$ for sorting and tree operations.

Space: $O(n)$ for tree and result.