Efficient Program to count values less then A[i] to the left of i

Question

Can someone provide NlogN complexity efficient Program to count values less then A[i] to the left of i ,

I know how to do in n square. If possible provide link.

Answer 1

One Approach that comes to my mind is reverse the array O(n), and your problem reduces to finding the number of elements smaller than A[i] that appear on the right side of A[i] which uses a BST and takes O(nlogn) storing the number of child nodes for every node.

This link will also be useful.

Answer 2

Use an index tree. Basically you go trough the array and update the index tree at index A[i]. For each number the answer is the sum before it in the index tree at the moment in which you reach it. The problem with this method is that it takes a lot of memory. If your numbers can be very big (or very small), you might need to compress them. Here is C++ code:

#include<iostream>
using namespace std;
const int MAX_N=1024; //maximum number of numbers
const int MAX_VAL=1023; //maximum value that the numbers take
const int MIN_VAL=-1024; //minimum value that the numbers take
int arr[MAX_N];
int indTree[MAX_VAL-MIN_VAL+1];
int ans[MAX_N];
int n;
void update(int ind, int val) //standard index tree function that updates the value at index ind
{
    while (ind<=MAX_VAL-MIN_VAL+1)
    {
        indTree[ind-1]+=val;
        ind+=ind&-ind;
    }
}
int sum(int ind) //standard index tree function that calculates the sum of element before ind
{
    int sum=0;
    while (ind>0)
    {
        sum+=indTree[ind-1];
        ind-=ind&-ind;
    }
    return sum;
}
void makePositive() //makes all numbers positive
{
    for (int i=0;i<n;++i)
    {
        arr[i]=arr[i]-MIN_VAL+1;
    }
}
void solve()
{
    makePositive();
    for (int i=0;i<n;++i)
    {
        //ans[i]=sum(arr[i]); choose one of the two
        ans[i]=sum(arr[i]-1); //the first one calculates the number of numbers smaller or equal to the current
        //and the second one calculates the number of numbers strictly smaller than the current
        update(arr[i],1);
    }
}
void input()
{
    cin>>n;
    for (int i=0;i<n;++i)
    {
        cin>>arr[i];
    }
}
void output()
{
    for (int i=0;i<n;++i)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    input();
    solve();
    output();
    return 0;
}

EDIT: The performance of the algorithm is O(Nlog(M)), where M is the range of the numbers. The space complexity is O(M). You can improve that by compressing the numbers, which would lower M. By doing this the performance won't increase since the compress function's performance is O(Nlog(M)), but the space complexity in the worst case will be O(N), because it is the number of different numbers and in the worst case, where they are all different, the number of different numbers is N. Here is the code using one possible compress function:

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int MAX_N=1024; //maximum number of numbers
int arr[MAX_N];
int arr2[MAX_N];
int indTree[MAX_N];
int ans[MAX_N];
int n;
map<int, int> newNum;
void update(int ind, int val) //standard index tree function that updates the value at index ind
{
    while (ind<=MAX_N)
    {
        indTree[ind-1]+=val;
        ind+=ind&-ind;
    }
}
int sum(int ind) //standard index tree function that calculates the sum of element before ind
{
    int sum=0;
    while (ind>0)
    {
        sum+=indTree[ind-1];
        ind-=ind&-ind;
    }
    return sum;
}
void compress() //compresses the numbers
{
    int currNum=1;
    for (int i=0;i<n;++i)
    {
        arr2[i]=arr[i];
    }
    sort(arr2,arr2+n);
    for (int i=0;i<n;++i)
    {
        if (newNum[arr2[i]]==0)
        {
            newNum[arr2[i]]=currNum;
            ++currNum;
        }
    }
    for (int i=0;i<n;++i)
    {
        arr[i]=newNum[arr[i]];
    }
}
void solve()
{
    compress();
    for (int i=0;i<n;++i)
    {
        //ans[i]=sum(arr[i]); choose one of the two
        ans[i]=sum(arr[i]-1); //the first one calculates the number of numbers smaller or equal to the current
        //and the second one calculates the number of numbers strictly smaller than the current
        update(arr[i],1);
    }
}
void input()
{
    cin>>n;
    for (int i=0;i<n;++i)
    {
        cin>>arr[i];
    }
}
void output()
{
    for (int i=0;i<n;++i)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    input();
    solve();
    output();
    return 0;
}