Calculation of the sum of the entire distance

Question

I was given n points on the line with their locations. I need to sum the distances between each pair of points. Is this possible with O (n) complexity.

Example: considering three points with their coordinates a (-1), b (-3), c (3). Amount Required: | -1 + 3 | + | - 1 - 3 | + | -3 - 3 | = 12

Please help me.

Answer 1

• Calculate the length of each sequential segment:

  for (int i=0;i<n-1;i++) len[i]=x[i+1]-x[i];
  

Note that this is for sorted points. If not, sort before calculating the length of the sequential segments.

2. , : SidePoints * rightSidePoints. , .

    for (int i=0;i<n-1;i++) contributionOfSegment[i]=len[i]*(i+1)*(n-i-1);
   

   i+1 leftSide points, n-i-1 rightSide points i-

3. - :

    int sum=0; for (i=0;i<n-1;i++) sum+=contributionOfSegment[i];
   

O(N) algo, O(Nlog(N)) (std sort), O(maxX) ( ). O(N)loglog(maxX)) O(N)*number_of_bits_in_maxX, 5N 32- , .

, . - O(N)*number_of_bits_in_maxX - . Van Emde Boas tree. findNext (x) - x O(loglogmaxX). O(loglogmaxX).

, Van Emde Boas :

• O(N)*number_of_bits_in_maxX for(i=0;i<n;i++) tree.insert(x[i]), x - .
• min in O(N)
• sortedArray [0] =
• for(int i=1;i<n;i++) sortedArray[i] = tree.findNext(sortedArray[i-1])

, : x sortedArray

, VEBTree , , N, log(N) , loglog(maxX), , , , . VEBTree , N , maxX - 32 64 .

Answer 2

, . , n . , Pi Pi+1. , Pi Di, Pi Pi+1 d, Di+1 = Di + i * d - (n - i - 1) * d, O (1), . .

, Pi Pi+1 Pi+1 d, Pi+1 d.

Answer 3

, . , , n = 3, n*(n-1)/2 ( , (a, b) (b, a) ), 3 :

n = 4 // number of points
p = [-3, -1, 1, 3] // our points

p[0], O(n) 12, |-3 + 1| + |-3 - 1| + |-3 - 3| = 2 + 4 + 6 = 12.

, , , , :

12 - (k - 1) * dist = 12 - (4 - 1) * 2 = 12 - 6 = 6

0 1 2, ( k-1=3). k 1:

6 - (k - 1) * dist = 6 - (3 - 1) * 2 = 6 - 4 = 2

, O(n), O(1) n-, O(n).

[12,6,2,0]=20, , .

Answer 4

, , . , n+1 . , (, ), . , , P0, - Pn. , n+1, n.

• , (minX) (maxX) x;
• ( BitArray[max - min + 1]);
• , , BitArray[minX + currentX] = true;
• int Distances[n] BitArray.
  • , minX;
  • Distances[0] = thisX - minX;
  • Distances.

O (maxX - minX), . O (n). , , (P0, P1) 0 (P1, P2) 1 (P2, P3) 2 ..

x : x, * , dn - P (n-1) Pn),

---*----------*------*--------*---------....--------*---
   ^          ^      ^        ^                     ^
   P0  (d0)  P1 (d1) P2 (d2)  P3  (d3)  ....  d(n)  Pn

O (n). .

:

(1 * (n - 1) * Distances[0]) +
(2 * (n - 2) * Distances[1]) + 
(3 * (n - 3) * Distances[2]) +
.
.
.
(1 * (n - 1) * Distances[n-1])

---

P0. P0 P1 Pn

= d(P0, P1)  + d(P0, P2)     + ... + d(P0, Pn)
= d[0]       + (d[0] + d[1]) + ... + (d[0] + d[1] till d[n-1])
= (n-1)*d[0] + (n-2)*d[1]    + ... + (n-1)*d[n-1]

In the same way, we take P1 and calculate its distance from P2 to Pn

Then take P3 ... until the final consideration of only the distance between P (n-1) and Pn

When summing these distances, we directly get the formula indicated above.

---

Therefore, if the points are set sorted , the runtime is O (n), and if the points are set unsorted , the runtime is O (maxX - minX), which is still growing linearly.