Process right to left. For each element:
Query: count of elements smaller than current (already in tree)
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: for sorting and tree operations.
Space: for tree and result.