0%

算法 - 二进制分组

资料

具体见 2013 年集训队论文《浅谈数据结构题的几个非经典解法》(作者:许昊然)。

为什么

  • 题目要求支持修改和查询操作。
  • 但是你只有一种不支持修改的算法,往往是通过预处理来支持快速查询操作。
  • 如果直接使用这种算法,可能要预处理很慢却要常常进行,查询很快却没几个,时间复杂度分配很不合理。
  • 于是你想到,可以通过分块使时间复杂度变得均匀合理。就是把每 $\sqrt n$ 个修改操作(假设修改操作共 $n$ 个)分为一组,然后每次需要预处理的长度上限就变小了,作为代价,增加了查询的时间。
  • 二进制分组是一种更为优秀的分组策略(具体和预处理复杂度和查询复杂度相关)。如果当前有 k 个修改操作,会按照 2 的幂将 k 分解从大到小的若干组。如果增加一个操作,分组的变化通过暴力删除和重建进行(当然如果可以合并的话那就只需要合并了)。(如 5 = 4 + 1, 6 = 4 + 2,从 5 增加到 6 就把原来那个大小为 1 的组删了,再将原来最后一个和新增加的那一个建一个大小为 2 的组)
  • 复杂度:
    • 单次查询复杂度 $\times \log n$,毕竟最多只有 $\log n$ 组嘛。
    • 总的预处理复杂度是单次的 $\log n$ 倍,具体证明见论文。

限制

  • 如果这不是一道强制在线题,我大可以选择时间分治。
  • 如果有支持在线的算法或数据结构,我就没有必要用 log 的代价把在线换成离线。
  • 要求修改操作的贡献可以任意次序累加。

例题

不存在的。这个算法想法很不错,不过很可能用不上。