Complexity of Set Difference
(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.