Find the summation of forces between all possible pairs of points?

Question

There are n points with each having two attributes:

1. Position (from axis)

2. Attraction value (integer)

Attraction force between two points A & B is given by:

Attraction_force(A, B) = (distance between them) * Max(Attraction_val_A, Attraction_val_B);

Find the summation of all the forces between all possible pairs of points?

I tried by calculating and adding forces between all the pairs

for(int i=0; i<n-1; i++) {
    for(int j=i+1; j<n; j++) {
        force += abs(P[i].pos - P[j].pos) * max(P[i].attraction_val, P[j].attraction_val);
    }
}

Example:

Points            P1 P2 P3
Points distance:  2  3  4
Attraction Val:   4  5  6

Force = abs(2 - 3) * max(4, 5) + abs(2 - 4) * max(4, 6) + abs(3 - 4) * max(5, 6) = 23

But this takes O(n^2) time, I can't think of a way to reduce it further!!

Answer 1

Scheme of a solution:

1. Sort all points by their attraction value and process them one-by-one, starting with the one with lowest attraction.
2. For each point you have to quickly calculate sum of distances to all previously added points. That can be done using any online Range Sum Query problem solution, like segment tree or BIT. Key idea is that all points to the left are really not different and sum of their coordinates is enough to calculate sum of distances to them.
3. For each newly added point you just multiply that sum of distances (obtained on step 2) by point's attraction value and add that to the answer.

Intuitive observations that I made in order to invent this solution:

1. We have two "bad" functions here (somewhat "discrete"): max and modulo (in distance).
2. We can get rid of max by sorting our points and processing them in a specific order.
3. We can get rid of modulo if we process points to the left and to the right separately.
4. After all these transformations, we have to calculate something which, after some simple algebraic transformations, converts to an online RSQ problem.