Process right to left. For each element:
Query: count of elements smaller than current (already in tree)
Update: add current element to tree
def countSmaller(nums):
# Coordinate compression
sorted_nums = sorted(set(nums))
rank = {v: i for i, v in enumerate(sorted_nums)}
n = len(sorted_nums)
tree = SegmentTree(n)
result = []
for num in reversed(nums):
r = rank[num]
# Count elements with rank < r
count = tree.query(0, r - 1) if r > 0 else 0
result.append(count)
tree.update(r, tree.query(r, r) + 1)
return result[::-1]
Time: for sorting and tree operations. Space: for tree and result.