Absolute distance from various points in O(n)

Question

I am stuck in question. The part of the question requires to calculate sum of absolute distance of a point from various points. |x - x1| + |x - x2| + |x - x3| + |x - x4| ....

I have to calculate this distance in O(n) for every point while iterating in array for eg:

array = { 3,5,4,7,5}
sum of distance from previous points

dis[0] = 0;
dis[1] = |3-5| = 2
dis[2] = |3-4| + |5-4| = 2
dis[3] = |3-7| + |5-7| + |4-7| = 9
dis[4] = |3-5| + |5-5| + |4-5| + |7-5| = 5

Can anyone suggest the algo to do this ? Algorithm for less than O(n^2) will be appreciated ( not necessarily O(n)).

Code for O(n^2)

REP(i,n){
   LL ans = 0;
   for(int j=0;j<i;j++)
      ans= ans + abs(a[i]-a[j])
   dis[i]=ans;
}

Answer 1

O(n log n) algorithm is possible.

Assume we had a datastructure for a list of integers which supported:

Insert(x)
SumGreater(x)
SumLesser(x)

Insert(x) inserts x into the list.
SumGreater(x) gives the sum of all elements greater than x, which are in the list.
SumLesser(x) gives the sum of elements < x.
NumGreater(x) gives the number of all elements greater than x.
NumLesser(x) gives the number of all elements < x.

Using balanced binary trees, with cumulative sub-tree sums and sub-tree counts stored in the nodes, we can implement each operation in O(log n) time.

To use this structure for your question.

Walk the array left to right, and When you encounter a new element x

You query the already inserted numbers for SumGreater(x) = G and SumLesser(x) = L and NumGreater(x) = n_G and NumLesser(x) = n_L

The value for x would be (G - n_G*x) + (n_L*x-L).

Then you insert x and continue.