线段树基础知识
在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在 OX 轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。 从简单说起，线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡，和静态二叉树一样，都是提前已经建立好的树形结构。针对性强，所以效率要高。这里又想到了一句题外话：动态和静态的差别。动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。
接着回到线段树上来，线段树是建立在线段的基础上，线段树处理的是一定的固定线段，或者说这些线段是可以对应于有限个固定端点的。处理问题的时候，首先抽象出区间的端点，例如说 N 个端点 ti(1 ≤ i ≤ N) 。那么对于任何一个要处理的线段（区间） 来说，总可以找到相应的 i,j ，使得 ti=a ,tj=b ,1 ≤ i ≤ j ≤ N 。这样的转换就使得线段树上的区间表示为整数，通过映射转换，可以使得原问题实数区间得到同样的处理。下图显示了一个能够表示 [1，10] 的线段树：每个结点都代表了一条线段。长度为1的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为，右结点代表的线段为[( a + b ) / 2 , b]。
线段树是一棵二叉树，树中的每一个结点表示了一个区间 。每一个叶子节点上 a+1=b, 这表示了一个初等区间。对于每一个内部结点 b-a >1 ，设根为 的线段树为 T(a ,b), 则进一步将此线段树分为左子树 T(a,(a+b)/2), 以及右子树 T((a+b)/2,b), 直到分裂为一个初等区间为止。线段树的平分构造，实际上是用了二分的