线段树
线段树英文名为Interval Tree，它是一种特殊的二叉树。\r\n\r\n由于这里有很多大一的同学，首先我们先简单介绍一下树的概念，大二大三的同学就权当复习吧。
树
一言以蔽之，每个节点 只能有一个前驱，可以 有多个后继的没有环的 数据结构（个人见解）\r\n\r\n一些概念：——对照Family Tree\r\n结点（Node），双亲（Parent），孩子（Child），兄弟（Sibling），祖先（Ancestor），高度（Height）
树的严格定义
树是由 n (n >= 0) 个节点组成的有限集合（记为T）。其中：\r\n如果 n=0，它是一棵空树，这是树的特例。\r\n如果 n>0，这n个节点中存在（且仅存在）一个节点作为树的根节点，简称为根(root)，其余节点又可分为m (m >= 0)个互不相交的有限集T1，T2，...，Tm，其中每个子集本身又是一棵符合条件的树，成为根的子树。
二叉树
如果限制树的一个节点最多有两个子节点（两个孩子），且这两个孩子是有顺序的，我们就称呼这样的树为二叉树。
二叉树的严格定义
二叉树是有限个节点的集合，这个集合或者为空，或者有一个根节点和两棵互不相交的成为左子树和右子树的二叉树组成。
二叉树的不是树！
二叉树和度为2的树是不同的。\r\n\r\n度为2的树至少有一个节点的度为2，而二叉树没有这种要求。\r\n度为2的树不区分左右子树，而二叉树是严格区分左右子树的。
二叉树的存储结构
顺序存储结构\r\n链式存储结构
二叉树的顺序存储结构
实现起来只需要开一个数组就好了\r\n\r\n可以快速获得一个节点的左右孩子、双亲
二叉树的链式存储结构
线段树
下面我们在回到线段树，还记得他的英文名么——Interval Tree.\r\nInterval是区间的意思，这也是它与普通二叉数的区别。\r\n什么区别呢？前面的介绍二叉树节点储存的都是某个值，而对于Interval Tree，节点储存的是一个区间（即区间的两个端点）。先看一个例子吧。
线段树
线段树的实现
顺序储存结构
线段树的建立
线段树的每个节点都表示一个区间[L, R]\r\n对于一个线段树的区间：\r\n若L < R，则必能被分为[L, M]和[M 1, R]，其中M = (L R) / 2\r\n若L = R，则为叶子节点。\r\n如果用数组实现，节点T的左儿子是T * 2，代表[L, M]区间，右儿子是Ｔ * 2 1，代表[M 1, R]区间。
线段树的建立
void Build(int T, int L, int R){\r\n if (L == R) {\r\n //Add values to the leave node;\r\n return;\r\n }\r\n int M = (L R) / 2;\r\n Build(T*2, L, M);\r\n Build(T*2 1, M 1, R);\r\n //Update the current node with his left son and right son.\r\n}
查询某个区间
在[L, R]中查询[LL, RR]的时候有一下三种情况：\r\n[LL, RR]被[L, M]包含，此时直接在[L, M]中查询[LL, RR]\r\n[LL, RR]被[M 1, R]包含，此时直接在[M 1, R]中查询[LL, RR]\r\n[LL, RR]被M从中间截断，此时在[L, M]中查询[LL, M]，在[M 1, R]中查询[M 1, RR]，然后将两个查询得到的结果进行Update, 返回Update的结果。\r\n这样递归处理就完成了查询。