Sum of Distances

“Sum of distances” is ambiguous, so first ask whether distance is between equal array values, points on a line, graph nodes, or all pairs. A common array version asks, for each index, the sum of absolute index differences to every equal value. Group indices by value; each group is naturally sorted by scanning order. For a group [p0,...,pm-1], maintain a prefix sum of positions. At position j, left contribution is j*p[j] - prefix, and right contribution is (total-prefix-p[j]) - (m-j-1)*p[j]. Add them for that index. This replaces an O(m squared) pair computation with O(m) per group, so total time is O(n) after grouping and space is O(n). For coordinate distances the same sorted-prefix identity applies; for graph distance, entirely different algorithms are needed. Do not infer a graph from this title.