Sum of distances between points on one-dimensional axis
Let us start with the formula for the sum of distances:
$$
\begin{align*}
D(\ell,r) := \sum_{i=\ell}^r [A_r - A_i] &amp;= (r-\ell+1) A_r - \sum_{i=\ell}^r A_i \\ &amp;= (r-\ell+1) A_r - \sum_{i=1}^r A_i + \sum_{i=1}^{\ell-1} A_i.
\end{align*}
$$
In time $O(n)$ we can compute an array $B_i = \sum_{j=1}^i A_j$: indeed, $B_0 = 0$, and $B_j = B_{j-1} + A_j$. The formula above then translates to
$$
D(\ell,r) = (r-\ell+1)A_r - B_r + B_{\ell-1},
$$
which can be computed in $O(1)$.