New answers tagged

1

Yes, let's require even less and say you're just interested in figuring out if the difference (similarly, intersection) is empty or not. It is trivial to have a quadratic-sized data structure with constant time query (by pre-processing everything) and also a linear-sized structure with linear query time (by just storing the sets trivially), and it's natural ...


4

(Sorry but not enough reputation otherwise this would be a comment.) Note that set difference is equivalent to set intersection with the complement i.e. $S_i\backslash S_j = S_i \cap \overline{S_j}$. Thus you could double the number of sets to $S_1, S_2, ...., S_k, \overline{S_1}, ..., \overline{S_k}$ and apply the set intersection pre-processing to the ...


Top 50 recent answers are included