Complexity of Set Difference Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes $S_i \backslash S_j$ for any $i$ and $j$?
Has this problem been studied before in the literature? If an output-sensitive algorithm (after preprocessing the sets) is not possible, what is the best complexity we can attain?
I found that there is a related problem which focuses on set intersection rather than set difference. To the best of knowledge, there is no output-sensitive algorithm for the case of set intersection.
(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 appropriate pairs.