The communication complexity of the set disjointness problem is $\Omega(n)$. The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint. Imagine Alice stores the data structure for the first set, and Bob stores the data structure for the second set; since they'll have to communicate $\Omega(n)$ bits to determine whether their sets are disjoint, any algorithm that works on these two data structures will also necessarily involve doing at least that much computation. It follows that testing disjointness of these two sets must take $\Omega(n)$ time, no matter what data structure you use, as long as each data structure is initialized separately.
Consequently, no such data structure exists.
Details: I'll elaborate on the proof more carefully, by sketching the reduction.
Suppose there was such a data structure, together with an algorithm $A$ that lets you test disjointness in $o(n)$ time. Since it runs in $o(n)$ time, it must involve examining at most $o(n)$ bits of data, and in particular, at most $o(n)$ bits of the data structure for the first set and at most $o(n)$ bits of the data structure of the second set.
So, here is a communication protocol for set disjointness. Initially, Alice initializes an instance of the data structure with her set, and Bob does the same with his set. Start running algorithm $A$, with both of them executing the algorithm in lockstep. Any time that algorithm $A$ examines a bit of the first data structure, Alice sends that bit to Bob. Any time that the algorithm examines a bit of the second data structure sends that bit to Bob. Now both Alice and Bob can execute the algorithm to completion. At the end of the algorithm, both Alice and Bob know whether their sets are disjoint are not. Also, the computation has taken $o(n)$ time, and they have sent only $o(n)$ bits of data (since it runs in $o(n)$ time, it can't send more than that), so we have a protocol for set disjointness with communication complexity $o(n)$. This is impossible, so our original assumption that such an algorithm $A$ exists must also have been impossible as well.
If algorithm $A$ is randomized, then it's easy enough to send the random bits to both parties. This doesn't affect the asymptotic complexity.
If the algorithm is in the RAM model, it can access $O(\log n)$ bits in a single operation, so we need to modify the above reduction slightly: if there is an algorithm $A$ for set disjointness that runs in $o(n/\log n)$ time, we obtain a communication protocol that sends $o(n)$ bits. It follows that any algorithm $A$ for set disjointness must take at least $\Omega(n/\log n)$ time in the RAM model. Since the RAM model is a standard assumption, perhaps it would be more reasonable to summarize this result as implying that disjointness queries must take at least $\Omega(n / \log n)$ time, in the worst case, no matter what data structure you use, as long as each instance of the data structure is initialized separately.
