Count of Smaller Numbers After Self — BIT + Coordinate Compress

Problem

For each element, count how many elements to its right are smaller.

Approach — BIT + Coordinate Compression

Coordinate compress values to indices [1..n]
Process from right to left: query BIT for sum [1..rank-1], then update rank
BIT stores count of elements seen so far

Time: O(n log n) | Space: O(n)

Solutions

Python

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)}
        n=len(sorted_unique)
        bit=[0]*(n+1)
        def update(i):
            while i<=n: bit[i]+=1; i+=i&(-i)
        def query(i):
            s=0
            while i>0: s+=bit[i]; i-=i&(-i)
            return s
        result=[]
        for num in reversed(nums):
            r=rank[num]
            result.append(query(r-1))
            update(r)
        return result[::-1]

C++

class Solution {
    vector<int> bit; int n;
    void upd(int i){for(;i<=n;i+=i&-i)bit[i]++;}
    int qry(int i){int s=0;for(;i>0;i-=i&-i)s+=bit[i];return s;}
public:
    vector<int> countSmaller(vector<int>& nums){
        vector<int> sorted=nums; sort(sorted.begin(),sorted.end());
        sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());
        n=sorted.size(); bit.assign(n+1,0);
        auto rank=[&](int v){return lower_bound(sorted.begin(),sorted.end(),v)-sorted.begin()+1;};
        vector<int> res;
        for(int i=nums.size()-1;i>=0;i--){int r=rank(nums[i]);res.push_back(qry(r-1));upd(r);}
        reverse(res.begin(),res.end()); return res;
    }
};

Complexity

Time: O(n log n) | Space: O(n)