线段树分治

简介

线段树分治通常用来解决数据结构只能做插入或者删除的问题。可以将其看作是用 \(\log\) 的复杂度将原问题中的一个插入或删除转化为撤销操作。

只能做插入或者删除的问题，典型的有链表、前缀max 等等。

基本思想

先记录所有修改的影响时间（即修改时间和撤销时间）。用线段树维护时间轴，使用类似标记永久化的思想，将线段树上对应区间进行标记。最后，扫一遍求出所有叶子节点的前缀的贡献（进入节点-操作-进入做儿子-进入右儿子-撤销），注意不能改为对每个点做单点查询的做法，否则极端情况下（所有修改都在根节点）会导致 \(O(nm)\) 的复杂度。