Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum
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.