二进制分组感觉是一种比较少见的数据结构维护方式。

能直接使用常规的单调队列或者单调栈写法。具体做法可见我之前写的 斜率优化学习笔记。这里详细讲一下二进制分组的做法。做法感觉网上说的理解都比较神秘实际上很好理解。其实这玩意和线段树是一个类似逻辑我们相当于第 i 次修改是在线段树上的 i 位置加上一个值。如果这个点还有一个兄弟节点那么就可以通过其父亲进行查询。那么我们就把这个点和其兄弟合并置于其父亲节点。其父亲再看能不能和兄弟合并以此循环下去直到没有兄弟。这样每个点都只合并了树高次是log⁡logn的时间复杂度的优势就体现在这。实际做的时候显然不需要模拟线段树只需要记录每个区间大小再不断合并即可。那么维护凸包同理。我们每次加入一个大小为 11 的凸包看看之前有没有大小和它一样的。有就不断合并直到没有。每次合并对凸包进行重构凸包有(log⁡)O(klogk)的单次处理方法因此构造的总的时间复杂度就是(log⁡2)O(nlog2n)的。查询显然只需要每一组求一个最值再在这些最值里面取出最值即可总的时间复杂度仍然是(log⁡2)O(nlog2n)的因为每次查询需要在一个块内二分一次。让我看看删除操作二进制分组处理删除通常有两种情况1. 可差分的信息如果维护的值满足可加减性例如求和、计数可以维护两个二进制分组结构一个存放增加的贡献另一个存放删除的贡献。查询时用“增加的答案”减去“删除的答案”即可。这种方法实现简单且时间复杂度不变。2. 不可差分的最值信息删除最后一个值对于最大值、最小值等不可差分的信息减法不再适用。如果只需要支持删除最后一次加入的元素即栈式删除可以考虑进行魔改将每一层的容量限制从“最多一个组”放宽为“最多两个组”。当某一层出现三个大小相同的组时才将前两个组合并成一个两倍大小的组第三个组继续保留。删除元素时直接从最后加入的组中移除对应元素。该方法保持了插入均摊(log⁡2)O(nlog2n)整体仍为(log⁡2)O(nlog2n)。3. 不可差分的最值信息删除任意值如果需要删除任意位置而非仅末尾的元素处理方式取决于内层数据结构是否支持删除。对于 KDT 等可以打标记的结构删除时先在各个组内查询到要删除的元素(log⁡)O(logn)的时间然后打上删除标记。查询时遍历组的过程中跳过被标记的元素。为了防止标记点堆积过多维护一个全局计数器当被标记删除的元素总数超过当前未删除元素数的一半时触发一次全局重构将所有未删除的元素重新分组。全局重构的代价是(log⁡)O(nlogn)假设内层结构重建是 (log⁡)O(klogk) 的均摊到每次删除上是(log⁡)O(logn)。对于凸包等不能打标记的结构凸包查询依赖二分和几何结构打标记会破坏这一前提——二分命中的点可能是已删除点而简单地“跳过它取相邻点”不能保证答案正确。因此凸包通常不支持打标记删除任意元素。如果确实需要支持删除一般有两种选择改用支持动态删除的凸包结构如平衡树维护凸壳放弃二进制分组的轻量优势。如果删除操作不多可以在每次删除后直接对该组暴力重构即删除后立即重建该组的凸包。单次代价为(log⁡)O(klogk)k 为该组大小若删除次数较少则整体可接受。