Sums of all pairs: possible less than quadratic?

Question

Is there an algorithm to prepare all sums of pairs of a list ($L$, size $n$, max value $m$) in $< O(n^2)$ such that query "does this sum of pairs exist" takes $< O(n)$? In other words, can max value $m$ be used to advantage?

E.g. in $L =\{1, 2, 4, 8\}$ and $m = 8$, all (distinct) sums of pairs are $S = \{2, 3, 4, 5, 6, 8, 9, 10, 12, 16\}$ (not given, calculate).

This may be possible using a divide-and-conquer on both $L$ and on the bits of each item. (N.B. the constraint keeps $S.size$ to $2m$, no need for size $O(n^2)$)

Answer 1

Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time.

Given the set $S$, construct the polynomial $P(x)=\Sigma_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication algorithm to compute $P^2(x)=P(x)*P(x)$ in $O(n \log n)$.

A value $q$ s a sum-of-pairs of $S$ if and only if the coefficient of $x^q$ in $P^2(x)$ is non-zero. Use binary search to look up the coefficient in $O(\log n)$ time ($P^2(x)$ is a polynomial of degree $2m$).

There are also less complicated (and less efficient, but still better than $O(n^2)$) multiplication algorithms that use divide-and-conquer such as Karatsuba multiplication ($O(n^{1.585})$ preprocessing).

Answer 2

The value $m$ can be used to advantage by simply sorting the list, and applying whatever $O(n)$ algorithm you had in mind on the list pruned to exclude items greater than the requested sum (which is $< 2m$). You get $O(m + log(n))$ complexity then.