Calculating force between n points placed on the x-axis

There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$.
We need to calculate the force on each charge by every other charge.
I need the exact force. Charges can be arbitrary. Inputs are the charges possibly in the form of an array.
Force is defined in the usual physical way.

I know an $O(n^2)$ algorithm to do the task. However, it can be done in $O(n\log n)$.

I have read about FFT, but I don't know how to apply it here. I know that we can multiply two degree $n$ polynomials in $O(n\log n)$. This problem is similar to that problem. Any help will be appreciated.

Suppose that the charges are $q_1,\ldots,q_n$. You need to calculate, for all $i$,
$$
F_i = q_i \sum_{j>i} \frac{q_j}{(i-j)^2} - q_i \sum_{jcirculant matrix. In order to obtain a circulant matrix, all you have to do is add $n-1$ dummy coordinates:
$$
\begin{bmatrix}
F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n \\ \ast \\ \vdots \\ \ast
\end{bmatrix} =
\begin{bmatrix}
0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \cdots & -1 \\
-1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} & \frac{1}{(n-1)^2} & \cdots & \frac{-1}{4} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
\frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 & 1 & \cdots & \frac{1}{(n-1)^2} \\
\frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \cdots & -1 & 0 & \cdots & \frac{1}{(n-2)^2} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
1 & \frac{1}{4} & \frac{1}{9} & \frac{1}{16} & \cdots & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \cdots & 0
\end{bmatrix}
\begin{bmatrix}
q_1 \\ q_2 \\ \vdots \\ q_n \\ 0 \\ \vdots \\ 0
\end{bmatrix}
$$
We don't really care about the $n-1$ asterisked entries. The new matrix is $(2n-1)\times(2n-1)$, and so FFT still runs in $O(n\log n)$. Of course, if your FFT works only for powers of 2, you need an extra padding step.

StackExchange Computer Science Q#71605, answer score: 3