Given a constant $c \in \mathbb{R}$ and two lists $X, Y \in \mathbb{R}^n$, I want to compute
$$ r = \sum_{x \in X} \sum_{y \in Y} \frac{c}{x+y+c} $$
Of course, this can trivially be done with $\mathcal{O}(n^2)$ arithmetic operations. However, I wonder whether there is any faster way of computing this sum. Specifically, my question is: Is there any approach to computing the above sum that requires only $\mathcal{O}(n)$ arithmetic operations?
The reason I'm wondering whether this is possible is that for the "inverse" sum $r = \sum_{x \in X} \sum_{y \in Y} \frac{x+y+c}{c}$, this can easily be achieved (if I did the maths correctly) be reformulating it as $r = \frac{1}{c}\cdot(n^2\cdot c + n\sum_{y \in Y}y + n\sum_{x \in X}x)$.
I take it that by "lists" $X, Y \in \mathbb{R}^n$ you mean $n$-tuples $X = (x_1, x_2, \ldots, x_n),$ $Y = (y_1, y_2, \ldots, y_n),$ where $x_i \in \mathbb{R},$ $y_j \in \mathbb{R}$ for $i, j = 1, 2, \ldots, n.$ Rather than using what seem to be confused notations $x \in X$ and $y \in Y,$ I shall write: $$ r = \sum_{i=1}^n\sum_{j=1}^n\frac{c}{x_i + y_j + c}. $$ (Let me know if this misrepresents your intentions.)
I don't know how to answer your question definitively, but I'll present an argument which suggests strongly that the answer is "no". I'll try to show that, if $n \geqslant 2,$ then $r$ cannot be expressed in the form $$ r = h(f(X), g(Y)) $$ for any differentiable functions $f \colon S \to U,$ $g \colon T \to V,$ $h \colon U \times V \to \mathbb{R},$ where $S, T$ are open subsets of $\mathbb{R}^n,$ and $U, V$ are intervals of $\mathbb{R}.$ (Don't worry if you're unfamiliar with the term open subset - it's not crucial.)
In a loose notation which I hope won't cause confusion (writing composites of linear maps, with nested parentheses, is also confusing), if we think of $h$ as a "function of two variables" $u = f(X)$ and $v = g(Y),$ $$ \frac{\partial r}{\partial x_i} = \frac{\partial h}{\partial u}\frac{\partial u}{\partial x_i} \text{ and } \frac{\partial r}{\partial y_j} = \frac{\partial h}{\partial v}\frac{\partial v}{\partial y_j}. $$ The important thing is that the partial derivatives of $u$ don't involve $Y,$ and the partial derivatives of $v$ don't involve $X,$ so the ratio of the partial derivatives of $r$ with respect to $x_i, x_{i'}$ is independent of $Y$ for all $i, i',$ and similarly the ratio of the partial derivatives of $r$ with respect to $y_j, y_{j'}$ is independent of $X$ for all $j, j'.$ But: \begin{align*} \frac{\partial r}{\partial x_i} & = -\sum_{j=1}^n\frac{c}{(x_i + y_j + c)^2} \quad (i = 1, 2, \ldots, n), \\ \frac{\partial r}{\partial y_j} & = -\sum_{i=1}^n\frac{c}{(x_i + y_j + c)^2} \quad (j = 1, 2, \ldots, n). \end{align*} It is enough to use just the first of these to derive a contradiction.
Take any point $X \in S$ such that no two of its coordinates $x_1, x_2, \ldots, x_n$ are equal. (Technically, this is possible because the set $S$ is open.) For $i = 1, 2, \ldots, n,$ write $$ p_i(Y) = \sum_{j=1}^n\frac1{(x_i + y_j + c)^2}, \text{ for } Y = (y_1, y_2, \ldots, y_n) \in T. $$ Our hypothesis is equivalent to the proposition that for every pair of indices $i, i'$ in $\{1, 2, \ldots, n\},$ the ratio $p_i(Y)/p_{i'}(Y)$ is independent of $Y.$ This is obviously unlikely, but we must obtain a contradiction from it.
Take any pair $i, i',$ it doesn't matter which. Our hypothesis implies that for $k = 1, 2, \ldots, n,$ $$ 0 = \frac\partial{\partial y_k}(\log p_i(Y) - \log p_{i'}(Y)) = \frac{-2}{p_i(Y)(x_i + y_k + c)^3} + \frac2{p_{i'}(Y)(x_{i'} + y_k + c)^3}, $$ therefore $$ \left(\frac{x_{i'} + y_k + c}{x_i + y_k + c}\right)^3 = \frac{p_i(Y)}{p_{i'}(Y)}, $$ which is independent of $Y,$ and therefore independent of $y_k.$ But we chose $X$ so that $x_i \ne x_{i'}.$ If, say, $x_{i'} > x_i,$ then the expression in the brackets is equal to $1 + (x_{i'} - x_i)/(x_i + y_k + c),$ which decreases strictly with $y_k,$ contradicting our hypothesis.
Therefore $r(X, Y)$ cannot be expressed in the form $h(f(X), g(Y))$ for any differentiable functions $f, g, h.$ $\ \square$
What this seems to show (although I admit that the argument is far from conclusive) is that there is no way to compute $r(X, Y)$ by first processing $X$ and $Y$ separately and then combining the results. This makes the prospects for an $\mathcal{O}(n)$ algorithm look rather bleak, I think.