本文共 879 字，大约阅读时间需要 2 分钟。

现在遇到的线段树共有如下3种：

1.插入点型

对于这种线段树，通常是向线段树中插入点，即对应一个叶子节点的信息，而线段树中所有节点也都是记录的关于以该点为根的子树中已插入的点的统计信息，询问通常是问线段树中某个区间对叶子节点的统计信息。

例题：

2.线覆盖型

对于这种线段树，与第三种有一下共同特点：所有询问和插入操作都是以区间为单位的，每次都是对一个区间进行操作。每个节点通常会用一个变量来记录以它为跟的子树的相关信息，在回溯过程中更新此变量。当操作的区间能完整的覆盖一个节点对应的区间时直接对该节点操作，不再向下操作。

这种线段树还有其独有的特点：当操作一个短线段时，这个短线段在线段树中由上至下运行到自己对应的位置，这个过程中会经过若干个对应长线段的节点，在经过长线段时，要把长线段的节点中的信息移动到其两个直接子节点中，然后再继续向下走。这样可以保证区间信息存储位置的在树中的纵向专一性，即树中节点的直系血亲之间只能有一个点记录信息。

原因如下：在这种线段树的题通常具有以下性质：(1)新插入线段与旧的线段重叠的部分的信息如果纵向分布，不存储在同一个节点中，则在回溯统计子树信息过程很难计算。(2)新插入的线段与旧线段的重叠部分可以只保存新线段信息，这样才能插入过程中完整覆盖一个节点时不用向下操作。

例题：

3.线保留型

这种线段树除了与第二种线段树的共同特点外，还有一个重要特性就是即使旧线段与新线段重叠了旧线段中的信息也仍然有意义，或者要求插入的线段必须保持在其插入的位置不向下迭代。

其中保持位置的一种典型情况就是有删除操作。删除并不是随意的删除，每次删除的线段与原来插入的线段相对应，只删除那些曾经插入过的线段。这种通常我们为了删除时候方便，在短线段向下运行经过长线段的过程中不会把长线段向下迭代，因为长线段是要被删除的，如果向下迭代删除时就没有办法对长线段原来的存储节点进行操作，只能对其许许多多的后代节点中的一些（那些被迭代到了的节点）进行操作，复杂度极高。这种线段树的题通常信息纵向分布也是可以回溯计算的。

以后遇到新的类型继续补充。

转载地址：http://zygsi.baihongyu.com/