Trie树维护集合相交性

这篇文章讲一个 trick, 他可以解决如下问题:

维护一个结构, 可以添加和删除集合, 可以询问: 对询问中给定的新集合, 结构中有多少集合与之不交?

用这个 trick, 可以在 $O(2^{|S|})$ 的时间复杂度内添加或询问一个集合 $S$ , 所以在多个小集合的时候比较有用。

对两个集合 $A$$B$ , 考虑 $B$ 的所有子集, 维护一个计数器 $cnt$ 。对每个子集 $S$ , 如果它也是 $A$ 的子集, 为 $cnt$ 加上 $(-1)^{|S|}$

$$cnt=\sum_{S\subset (A\cap B)}(-1)^{|S|}=\sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^i\times 1^{|S|-i}=(1-1)^{|S|} $$

$A\cap B=\emptyset$ 时形式上是$0^0$不定式, 根据定义式计算, 发现它有由空集贡献的 1 。于是 $cnt$ 就标志着 $A\cap B$ 是否为空: 为空时 $cnt=1$ , 否则 $cnt=0$

现在我们维护一个 Trie 树, 每个节点代表一个集合。当添加集合 $A$ 时, 给它的所有子集对应的节点权值加一。删除时, 就为所有子集对应的节点权值减一。可以注意到空集对应节点的权值就代表当前结构中维护的集合个数。

然后考虑询问: 设在询问 $S$ , 对所有 $S'\subset S$, 如果 Trie 树中有对应 $S'$ 的节点, 就为计数器加上 $(-1)^{|S'|}\times tr ie[S']$。这样, 对结构中维护的每个集合, 若它和 $S$ 不交, 它对计数器的贡献就是 1 , 否则是 0。于是计数器的值就代表了结构中与 $S$ 不交的集合个数。