Surpasser Count

An element Y is said to be the surpasser of element X if it is a greater element on the right of X. ie, if X = arr[i] and Y = arr[j], i<j and Arr[i] < Arr[j].

Given an array of size N containing distinct integers, find the number of surpassers for each of its elements.

• Time : O(nlogn)
• Space : O(n)

class Solution{
    int fenwick[1000001];
    void update(int n) {
        while(n < 1000001) {
            fenwick[n] += 1;
            n += n & -n;
        }
    }
    int query(int n) {
        int res = 0;
        while(n) {
            res += fenwick[n];
            n -= n & -n;
        }
        return res;
    }
public:
    vector<int> findSurpasser(int arr[], int n) {
        memset(fenwick, 0, sizeof fenwick);
        vector<int> res(n);
        for(int i = n - 1; i >= 0; i--) {
            res[i] = query(1000000) - query(arr[i]);
            update(arr[i]);
        }
        return res;
    }
};