title: Absolute distance from various points in O(n)
body: <p>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| ....</p>
  
  <p>I have to calculate this distance in O(n) for every point while iterating in array for eg:</p>
  
  <p><strong>array = { 3,5,4,7,5}</strong><br>
    <em>sum of distance from previous points</em></p>
  
  <pre><code>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
  </code></pre>
  
  <p>Can anyone suggest the algo to do this ?
  Algorithm for less than O(n^2) will be appreciated ( not necessarily O(n)).</p>
  
  <p>Code for O(n^2)</p>
  
  <pre><code>REP(i,n){
     LL ans = 0;
     for(int j=0;j&lt;i;j++)
        ans= ans + abs(a[i]-a[j])
     dis[i]=ans;
  }
  </code></pre>