Count smaller elements right
Your task
Given an integer array nums, return a new array counts where counts[i] is the number of elements to the RIGHT of nums[i] that are strictly smaller than nums[i]. Values may be negative. Length up to 10^5, so an O(n^2) double loop is too slow, use a modified merge sort (count cross-pair inversions) or a Binary Indexed Tree over compressed values for O(n log n).
Examples
count_smaller(nums: list[int]) -> list[int]Example 1
Input
count_smaller([5, 2, 6, 1])Output
[2, 1, 1, 0]