前言

当你遇到有一些类似线性查找的题的时候，刚好数据特别大的时候，那么线段树这个东西就很好用了，但是线段树的概念就是学习线段树的一大难点，要想学好线段树，就要先了解线段树。

线段树的概念

1. 线段树是一棵二叉树，其节点表示的是一个区间 [ x , y ]

2.

每一个叶子节点表示了一个单位区间，根节点表示的是“整体”的区间。

3. 每个非叶子节点的区间 [ x , y ]

其左儿子节点的区间 [ x , ( x + y ) / 2 ]

其右儿子节点的区间 [ ( x + y ) / 2 +１，ｙ]

线段树的特点

线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。

线段树的建立

这个就要用递归来完成了