二进制分组的删除操作

· · 算法·理论

分两种情况讨论。下文中 n 均表示当前未删除元素个数；不考虑内层数据结构复杂度。

末尾删除

若内层数据结构不支持删除或懒惰删除，则二进制分组只能支持在末尾删除。

直接删除的问题在于如果 n 在 2^k 和 2^k-1 之间横跳复杂度就炸了。

考虑魔改二进制分组：允许最多两个 2 的次幂出现，即当出现三个 2^k 时再合并为 2^{k+1} 和 2^k，而不是出现两个就合并。删除时将当前最小的分组 2^k 拆成 2^0\sim2^{k-1}。

对于每个 k，刚重构（合并或拆分）后再插入或删除 \Omega(2^k) 个元素后才会进行一次重构，所以均摊复杂度仍为 \mathcal O(\log n)。

任意位置删除

此时内层数据结构支持删除，只是我们要求复杂度与 n 而不是插入次数相关。kdt 是此类问题的一个典型，kdt 不能方便地支持插入，但是可以通过打标记等手段“删除”已有的点。

处理方式很简单，首先在每个组里进行查询找出要删除的元素，此部分 \mathcal O(\log n)；然后，维护当前（全局）删除了多少元素，大于一半就全部重构。删除 \Omega(n) 个元素重构一次，重构花费 \mathcal O(n\log n)，均摊单次删除 \mathcal O(\log n)。