线段树相关

· · 个人记录

最近种了很多线段树。
主席树：主要用来求第l~r次的修改操作形成的线段树，主要利用了前缀和的思想，和线段树的可减性。主席树的每个版本都有上一个版本更新而来，对于操作数量为n，值域为m的主席树，一次修改增加logm个节点，他的空间复杂度是nlogm。由于查询和修改与普通线段树一样，是O(logm)级别的。但是主席树是一旦建好就不能修改了，如果要修改的话，可以使用树套树。

李超线段树：维护线段y=kx+b的最值，对于直线，可以看作是从0~N范围的线段。李超线段树的维护主要运用了标记永久化的技巧，他每段区间只维护一条优势线段：指在这段区间中在mid处取得最大值的线段，然后再去递归处理。李超线段树不能标记下传，所以靠标记永久化的方法保证了每次修改的复杂度为logn。李超线段树可以用来维护线段的最值，也就是可以用来优化形如y=kx+b的动态规划。

线段树合并：在一棵树上，如果只想统计子树的信息，而不想被其他树枝干扰，可以用线段树合并的方法。在每个叶子节点建立线段树，然后将他们的信息合并到他们的父亲节点，那么他们的父亲节点的信息就只有当前子树的信息。线段树合并还可以优化dp，对于状态为x,y，以x为根的子树内状态为y，可以考虑把y放到线段树上，通过线段树合并来转移状态，大大优化了时间复杂度。线段树合并大多时候需要离线处理。将两颗线段树合并到一起，复杂度为较小的那颗树的大小，因为当一颗子树为空的时候，就直接返回另一颗子树了，所以线段树合并的时间复杂度和树上启发式合并一致，为O(nlogn)。对了，上文的李超线段树也是可以合并的，注意合并的时候每次都要更新。

线段树分治：当一个修改操作的生效时间为一个区间时可以考虑线段树分治，线段树分治处理一个区间时，先处理对这个区间都生效的所有操作，然后处理左区间和右区间，然后将所有操作撤销。正是因为操作必须要支持撤销，所以并查集不能进行路径压缩，要安秩合并。线段树分治的用法也有很多，比如说将询问区间最大值的时候可以把询问放到树上，再套整体二分。诸如此类的用法还有很多很多，都看考场的理解和发挥。
树套树，看起来不是很难，遇到题再补。
楼房重建线段树：线段树上前（后）缀max（min）问题，修改pushup函数，从右儿子递归转移，复杂度升为 O(nlog^2n)