0%

代码详见模板库。模板题 EOJ 3389-3393。

  • Q: 要不要把 n 补成 2 的幂?

  • A: 这个无所谓,但如果要写成自底向上,那么还是需要的,否则无法直接定位叶节点。

  • Q: pushdown 之后要不要立即 maintain?

  • A: 不用立即 maintain,但迟早是要的。但是立即 maintain 很可能会重复 maintain,增加超时风险。

  • Q:query 的时候要不要 pushdown?

  • A: 如果不要的话,查询时应该把之前访问到的结点的标签的效果累加起来,并作为参数递归下去。如果要的话,代码会更加具有普适性(比如 treap 只能选择 pushdown 标签,因为结点之间相对位置会改变)。

  • Q: maintain 的时候是否考虑当前结点的标签?

  • A: 都可以。如果考虑了,那么查询的时候就不要考虑当前结点的标签了,反之亦然。

  • Q: query 的时候先考虑 set 标签还是先考虑查询区间包含当前区间?

  • A: 都可以,但是先考虑 set 会快一些。

  • Q: 根节点是 0 还是 1?

  • A: 都可以,但好像 1 比较符合人性。

  • Q: 听说空间开三倍就够了?

  • A: 那可能就 GG 了,实测 4 倍是必要的。

其他注意事项:

  • maintain 函数要写得保证即便是重复调用也不会出错。
  • pushdown 子节点必须 maintain,尤其是那个没有递归下去的子节点。
  • 打完 set 标记后 add 标记必须清空。

资料

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

为什么

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