Count Smaller Numbers After Self — Merge Sort or Binary Indexed Tree

# Python — merge sort with index tracking
def countSmaller(nums):
    n = len(nums)
    counts = [0]*n
    indices = list(range(n))

    def merge_sort(arr):
        if len(arr) <= 1: return arr
        mid = len(arr)//2
        left = merge_sort(arr[:mid])
        right = merge_sort(arr[mid:])
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if nums[left[i]] <= nums[right[j]]:
                counts[left[i]] += j  # j elements from right already merged
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        while i < len(left):
            counts[left[i]] += j
            merged.append(left[i]); i += 1
        merged.extend(right[j:])
        return merged

    merge_sort(indices)
    return counts

# Python — BIT (Fenwick Tree)
def countSmaller(nums):
    # Coordinate compress
    sorted_unique = sorted(set(nums))
    rank = {v:i+1 for i,v in enumerate(sorted_unique)}
    n = len(nums); m = len(sorted_unique)
    bit = [0]*(m+1)

    def update(i):
        while i<=m: bit[i]+=1; i+=i&(-i)
    def query(i):
        s=0
        while i>0: s+=bit[i]; i-=i&(-i)
        return s

    res = []
    for x in reversed(nums):
        r = rank[x]
        res.append(query(r-1))
        update(r)
    return res[::-1]