转载请注明作者：phylps@bmy
出处：http://duanple.blog.163.com/blog/static/70971767200922110494318/
第一层次
线段树的本质在于将一条线段区间分成一些小的子段，树状数组可以看成一种线段树。对于该区间内的一些线段便可以用这样的一些子段来表示，同时有这样的定理。任何一个长为L的线段都可以用不超过2*logL个子段表示。这样对于插入一个线段便可以在logn时间内解决。而线段树，则是通过这样的使用线段子段的组合，来表示现在出现的线段，而具体的方式则是通过对于一个子段的cout计数来表示的。同时一条线段在树中，只会被真实的表达一次，即只有真正组成它的那些子段会被计数，而当子段已经计数，就可以结束，而子段下的子段不会被重复计数。
同时要求删除的线段都是曾经插入的线段，这样才能正确的保证删除的那些就是一开始插入分裂的那些子段，保证前后的一致。
线段树的结构在于，它以树中子段的形式保存了出现的所有线段。其结构所维持的不变性不在于维护了所有属于该节点代表区间的那些段，而是节点维护了真正被分裂到当前区间的那些子段所包含的属性值。如果放在线段树上来说，就是只维护真正分裂到该节点的子树上的那些子段构成的属性。
一个常见的线段树结构是这样的
举例说明：一条线段【3，7】将被图中的【3，5】【5，7】这两个节点所表示。这样比如我们设立一个属性值，cover表示在节点所示区间内的线段并的长度，这样我们在维护节点[3,4]的属性时，虽然[3,7]这条线段，的确覆盖了[3,4]这段，但是我们的树结构上这个cover值仍然是0，因为[3,4]只维护了由它的子树上的那些段构成的该属性的值。而【3，7】的分裂并不包含【3，4】这个子段。但是如果放到一维区间看，【3，4】实际上也被【3，7】覆盖了。所以，线段树上节点的属性，并不是放到一维空间内的线段区间来考虑，而是要放到线段树上的被分裂到该节点的子树上的那些段来考虑。
线段树的基本结构如上，同时也支持一些基本操作，包括：线段的插入，删除，更新。同时通过给节点增加属性，可以得到一些关于这些线段的统计属性，而这个统计属性一般都保存在根节点呢。包括线段计数即某条线段被所有覆盖的次数，或者是某个点被覆盖的次数，这个只需要通过累加其父亲中count的值即可。
另有两个基本属性，即线段的测度，也就是所有线段并的长度，还有线段并之后形成的独立线段树。这两个属性常被用到计算几何中。其中测度在计算矩形并的面积，独立线段数则用于计算矩形并的周长。
所以基本的线段树操作，包括线段树的建立，线段的插入，删除，查询。以及count，测度及独立线段树属性的维护。这应当属于线段树应用的第一层次。
题目参考：
第二层次
另一方面，线段树，除了表示一些线段，经过一些改变，也是可以用来表示离散点的。观察可以发现，实际上每个节点的端点不再重合，而最下面的叶子也不再是长度为1的两个，而是继续分裂。
这个类型的结构，适合去处理那些关于数组的问题，比如rmq，区间k大数，区间和，以及一切用树状数组解决的那些。
另这个类型，实际上可以看成是所有线段都是单位元线段的情况。
关于线段树使用数组实现的空间耗费分析
题目参考：
第三层次
观察上面可以发现，上面的删除操作保证了是在插入的线段上进行，而查询也是只需要观察根节点维护的属性，就是我们需要的信息。然后有时候会碰到更复杂的应用，完全不遵守上述条例。
对于这种情况，则需要对线段树及其操作进行进一步的修改，使其复杂度不至于降低到线性，而是依然可以保证logn的水平。