Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

There are two operations as follows:

insert(num): insert num into the data structure.

find(sum): return a pair(a, b) such that a + b = sum, if no such pair exists return -1

How such data structure could be designed, possibly with find $\in o(N)$ and insert $\in o(\log N)$ operations?

It's unlikely that a data structure exists that supports both $insert(\cdot)$ and $find(\cdot)$ queries in $o(n/\log^2 n)$ time, since if it did, then we could use it to solve the 3SUM problem in $o(n^2/\log^2 n)$ time, beating the best known algorithm for this problem, which takes $O(n^2 (\log \log n)^{O(1)}/\log^2 n)$ time.

In 3SUM, we are asked to find 3 distinct elements that sum to zero in a list of distinct integers $x_1, \dots, x_n$. We can reduce this problem to your problem as follows:

• For each $i$ from 1 to $n$:

• Call $find(-x_i)$. If this succeeds, with return value $(x_a, x_b)$, then $x_a, x_b, x_i$ are all distinct and sum to zero: return TRUE.

• Call $insert(x_i)$.

• Return FALSE.

StackExchange Computer Science Q#103440, answer score: 4