二进制分组技巧
二进制分组技巧
考虑我们手工维护一个二进制序列，其仅支持增加1操作，以及查询某一二进制位操作。
我们可以直接维护一个二进制数组，之后每次查询直接数组+偏移$O(1)$可以得到，而增加操作可以直接暴力进位计算即可。很显然假设增加1操作次数上限为$n$，那么每次增加操作的时间复杂度都最多为$O(\log_2n)$。
事实上我们可以为增加操作算出更加准确的更优的时间复杂度。由于最低位（第0位）每次增加操作都会改变，第i位每$2^i$次增加操作执行一次。因此可以得出摊还时间复杂度为：
\[\sum_{i=0}^{\log_2n}\frac{n}{2^i}\leq 2n\]因此一次增加操作所需时间复杂度为常数，比想象中的好。
现在我们来讲一下什么是二进制分组技巧。想象我们要维护一个有序列表，其支持增删改查，取前驱后继的能力。当然我们自然而然会想到平衡树，但是我们可以直接用二进制分组思路来完成这些操作。
我们一开始维护一个特定长度的数组$s$（一般32或64足矣）。数组的第$i$个元素要么为空，要么放长度为$2^i$的列表。
之后每次增加x操作，我们创建一个有序列表$l$，其中仅包含x。之后我们把列表放入数组中。由于$l$的长度为$1=2^0$，因此应该放在s[0]上。如果s[0]为空，那么直接放入，否则发生冲突，我们需要将s[0]和$l$合并为有序列表，同时将s[0]设置为空，我们将合并后的列表重新加入$s$中，重复上面过程直到被加入为止。
很显然每次加入操作可能会触发很多次合并，那么时间复杂度应该是多少呢。创建大小为1的列表直接放入的情况非常简单，$O(1)$，发生合并时，我们可以将费用摊给比合并的两个列表中的元素，被合并的元素所处的数组下标加了1，而每个元素所处最大数组下标为$\log_2n$，因此总的时间复杂度为$n\log_2n$，和平衡树一致。
查询操作怎么实现呢，由于最多有$\log_2n$个有序列表，其中每个列表长度都小于$n$，因此对每个列表二分即可。时间复杂度为$O((\log_2n)^2)$。
先来讨论删除操作，我们可以为每个值统计一个出现次数，同时删除就是减少出现次数而已。
取前驱后继可以直接暴力二分可能的值，时间复杂度为$O((\log_2n)^3)$。
修改操作可以由删除+新增代替，删除旧值，增加新值。
最后遍历操作，我们可以维护$O(\log_2n)$个指针，之后每次选最小的那个就行了。总的时间复杂度为$O(n\log_2n)$。
二进制分组技巧大概就讲完了，暴力合并，统计贡献，非常简单，但是却可以为我们解决非常多的在线问题。
现在我们把二进制分组技巧用在实际的问题上，解决codeforces上的这道题。这个问题要求我们在线维护一个允许增加新字符串和删除旧字符串的AC自动机。首先删除操作，我们可以变更为在另外一个自动机上的增加操作，真正结果就是两个自动机的结果的差分。而新增操作，我们可以用二进制分组来完成，每次新增等价于构建一个包含一个字符串的AC自动机并扔入二进制分组中，执行些必要的合并而已，合并可以通过重建一个AC自动机实现。可以证明总的时间复杂度为：
\[\sum_{i=0}^{\log_2n}\frac{n}{2^i}2^i=n\log_2n\]