算法 - 二进制分组

资料

具体见 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 的代价把在线换成离线。
• 要求修改操作的贡献可以任意次序累加。

例题

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