我自己在学这些数据结构以及算法的时候，网上的博客很多都是给出一个大致思想，然后就直接给代码了，可能是我智商太低，思维跳跃没有那么大，没法直接代码实现，而且有些学完之后也没有得到深层次的理解和运用，还是停留在只会使用模板的基础上。所以我希望我写的东西能让更多的人看明白，我会尽量写详细，也会写出我初学的时候哪些地方没有理解或者难以运用，又是怎样去熟练的使用这些东西的。可能还是不能让所有的人都读明白，但我尽量做的更好。

　　线段树是一种二叉搜索树，什么叫做二叉搜索树，首先满足二叉树，每个结点度小于等于二，即每个结点最多有两颗子树，何为搜索，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。

　　线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。更可以扩充到二维线段树（矩阵树）和三维线段树（空间树）。对于一维线段树来说，每次更新以及查询的时间复杂度为O(logN)。

　　常用的解决RMQ问题有ST算法，二者预处理时间都是O(NlogN)，而且ST算法的单次查询操作是O(1)，看起来比线段树好多了，但二者的区别在于线段树支持在线更新值，而ST算法不支持在线操作。

　　这里也存在一个误区，刚学线段树的时候就以为线段树和树状数组差不多，用来处理RMQ问题和求和问题，但其实线段树的功能远远不止这些，我们要熟练的理解线段这个概念才能更加深层次的理解线段树。

　　现在请各位不要带着线段树只是为了解决区间问题的数据结构，事实上，是线段树多用于解决区间问题，并不是线段树只能解决区间问题，首先，我们得先明白几件事情。

　　每个结点存什么，结点下标是什么，如何建树。

　　下面我以一个简单的区间最大值来阐述上面的三个概念。

　　对于A[1:6] = {1,8,6,4,3,5}来说，线段树如上所示，红色代表每个结点存储的区间，蓝色代表该区间最值。

　　可以发现，每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。

　　上面的每条结论应该都容易看出来。那么结点到底是如何存储区间的呢，以及如何快速找到非叶子结点的孩子以及非根节点的父亲呢，这里也就是理解线段树的重点以及难点所在，如同树状数组你理解了lowbit就能很快理解树状数组一样，线段树你只要理解了结点与结点之间的关系便能很快理解线段树的基本知识。

　　对于一个区间[l,r]来说，最重要的数据当然就是区间的左右端点l和r，但是大部分的情况我们并不会去存储这两个数值，而是通过递归的传参方式进行传递。这种方式用指针好实现，定义两个左右子树递归即可，但是指针表示过于繁琐，而且不方便各种操作，大部分的线段树都是使用数组进行表示，那这里怎么快速使用下标找到左右子树呢。

　　对于上述线段树，我们增加绿色数字为每个结点的下标

　　则每个结点下标如上所示，这里你可能会问，为什么最下一排的下标直接从9跳到了12，道理也很简单，中间其实是有两个空间的呀！！虽然没有使用，但是他已经开了两个空间，这也是为什么无优化的线段树建树需要2*2k（2k-1 < n < 2k)空间，一般会开到4*n的空间防止RE。

　　仔细观察每个父亲和孩子下标的关系，有发现什么联系吗？不难发现，每个左子树的下标都是偶数，右子树的下标都是奇数且为左子树下标+1，而且不难发现以下规律

　　具体证明也很简单，把线段树看成一个完全二叉树（空结点也当作使用）对于任意一个结点k来说，它所在此二叉树的log2（k） 层，则此层共有2log2(k)个结点，同样对于k的左子树那层来说有2log2(k)+1个结点，则结点k和左子树间隔了2*2log2(k)-k + 2*(k-2log2(k))个结点，然后这就很简单就得到k+2*2log2(k)-k + 2*(k-2log2(k)) = 2*k的关系了吧，右子树也就等于左子树结点+1。

　　是不是觉得其实很简单，而且因为左子树都是偶数，所以我们常用位运算来寻找左右子树