线段树，一段段的树

线段树这个名称充分体现了程序员们的直男思维，名字中蕴含着线段树的核心。线段树与区间树类似，将一个区间划分为一些单元区间，将每个单元区间存储在节点中。 线段树是一种二叉搜索树。什么是二叉搜索树？首先要满足二叉树的定义，每个节点的度都小于等于2。其次作为搜索树，在树上进行搜索就可以得到答案。 线段树有很大的使用范围，可以用于线维护修改和查询区间上的最值、求和，并且可以扩充为二维线段树（矩阵树）和三维线段树（空间树）。在线段树上的每一次更新和查询的时间复杂度都是$O\left(n\log n\right)$。 比起大堆的文字，果然还是图示比较容易理解线段树的含义。来人！上图！  这是一个只有聪明人才能看见节点的线段树哒！你没有看见？emmmm，因为它确实是空的。让我们给它一个数列A[1:6]={1,8,6,4,3,5}。首先，根节点储存整个区间，接着我们将这个区间像百奇一样掰断！左一半，右一半。于是根节点的左右两个节点分别分到了[1:3]、[4:6]这两个区间。以此类推，我们对每一个节点都进行这样的操作，直到无法分割为止。于是是我们得到了这样的一棵树。  接着从叶子节点求出我们要求的值（这里以最大值做示范），可以看出父亲的值就是两个子节点存储的值中的最大值，于是我们从底部向上回溯定义。  这样的一棵树就是线段树。那该任何存储这棵树呢？对于一个区间，最重要的显然是l，r这两个范围。但是由于l和r可以通过递归传参得到，所以我们便可以考虑使用数组来存储线段树。既然要用数组，那我们得先给每一个节点编上号。  这样的编号方式，我们不难发现其中规律： $left=father*2$ $right=father*2+1$ 这样线段树父子节点之间在数组中的下标关系就可以确定了，由此也可以看出无优化的线段树需要$2* 2^{k}$的空间，所以一般开$4* n$的空间防止RE。而在代码中，往往使用位运算来计算节点的下标，因为位运算的速度更快（~~玄学~~）。 建树代码： ```cpp void push_up(int now) { t[now]=max(t[now<<1],t[now<<1|1]); //写函数是好习惯 return; } void build(int now,int l,int r) { if(l==r) { t[i]=d[i]; //如果区间大小为1,则最大值确定 return; } int m=(l+r)/2; build(now<<1,l,m); //向下搜索 build(now<<1|1,m+1,r); push_up(now); //更新父节点 return; } ```