Count of Smaller Numbers After Self

Intuition

Reading the array from the back means everything already inserted into the tree lies to the right of the current element. The question 'how many are smaller' becomes 'how many inserted ranks are below my rank', which a Fenwick tree answers as a prefix sum of counts. Compressing the raw values to consecutive ranks keeps the tree small even when values are sparse or negative, and each insertion and query costs only logarithmic time.

Algorithm walkthrough

1. 1Sort the distinct values and assign each a 1-based rank so lookups map any value to a small index.
2. 2Create a Fenwick tree of counts sized to the number of distinct values.
3. 3Traverse the array from the last element to the first. For the current value, query the tree for the total count of ranks strictly below its rank; that is its answer.
4. 4Insert the current value by adding one at its rank in the tree.
5. 5Return the answers array once the traversal completes.

Implementation

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sorted_unique = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
        m = len(sorted_unique)
        tree = [0] * (m + 1)

        def update(i: int) -> None:
            while i <= m:
                tree[i] += 1
                i += i & (-i)

        def query(i: int) -> int:
            s = 0
            while i > 0:
                s += tree[i]
                i -= i & (-i)
            return s

        result = [0] * len(nums)
        for idx in range(len(nums) - 1, -1, -1):
            r = rank[nums[idx]]
            result[idx] = query(r - 1)
            update(r)
        return result