§ Sum of absolute differences of an array
 We are given an array
a[:]
and we are asked to compute the sum of differences $\sum_{i=1}^n \sum_{j=i+1}^n a[i]  a[j]$.  To compute this efficiently, first sort
a[:]
into a sorted array s[:]
. For simplicity, say we have N = 4
.  Now see that if we write down the values for
N=4
, we will see:
D =
s[1]  s[2] + s[1]  s[3] + s[1]  s[4] +
s[2]  s[3] + s[2]  s[4] +
s[3]  s[4]

i < j
implies s[i] < s[j]
as s
is sorted. So each of the terms (s[i]  s[j])
is negative. We thus flip the terms, giving:
D =
(s[2]  s[1]) + (s[3]  s[1]) + (s[4]  s[1]) +
(s[3]  s[2]) + (s[4]  s[2]) +
(s[4]  s[3])
 Note that
s[1]
is always negative, so it will have coefficient 4
on grouping.  See that
s[2]
was positive in the grouping (1, 2)
, and was negative in the groupings (2, 3)
and (2, 4)
. So 2
will have a coefficient +1*(21) 1*(4  2)
.  Similarly,
s[3]
was positive in the grouping (1, 3)
and (2, 3)
and was negative in the grouping (3, 4)
.  In general,
s[i]
will be positive when paired with [1, 2, ..i1, i)
and negative when paired with (i, i+1, i+2, \dots n]
. So s[i]
will contribute a coefficient of +1*(i1)  1*(ni)
[using the formula that for intervals [l, r)
and (l, r]
the number of elements is (rl)
]