数据结构——线段树

作为一枚蒟蒻，学习是重要的。最近，我接触了一种新数据结构——线段树。我一见，只是全身懵逼，[流汗]，怎么这么蓝？

于是，我开始努力学，努力学······（此处省略INF个努力学）,决定写一下博客。

线段树是一棵二叉树，并与分治有着密切关系。

就说说最简单的一个例子，1~10的区间线段树。

这棵线段树吧1~10这个区间不断de二分，最终分成一个一个数的叶节点，因此来储存一个区间。

这里多次提到了——  区间  ——二字

于是，蒟蒻猜想，传说中的线段树和区间有关！

那么，问题来了

为什么要用线段树呢？

用数组不就行了？

其实我也不知道

BUT，这是一个有用的数据结构    大佬们都这么说

好，不开玩笑了，线段树是一个非常强   如xxzh&Rye_Catcher&TYQ······(dalao de 集合)

的数据结构。

它支持区间询问，单点修改，区间修改作用的数据结构，还可以配合离散化进行大力时间优化，让算法复杂度大大降低。

蒟蒻：这样好

于是，我就开始研究。

线段树，既然是树，就要定义数组去储存它。建造一棵线段树其实很简单，类似于二叉树，却强于二叉树。

直接看代码：

1 void build(int k,int l,int r)                 //k:当前节点编号  l，r为k所代表的区间 2 { 3      if(l==r)                                 //区间只有一个节点，即叶节点，建树后return 4      { 5           mi[k]=v;                            //对应区间的最小值在原序列中的对应值  6           return; 7      } 8      int mid=(l+r)/2;                         //构造中间数 9      //递归定义左子树和右子树,由完全二叉树的性质可得左子树编号为2*k，右子树编号为2*k+110      build(k*2,l,mid);                       11      build(k*2+1,mid+1,r);12      mi[k]=min(mi[k*2],mi[k*2+1]);//更新线段树13 }

注释都写在code里了

这是一个递归定义的函数，以叶（区间长为一的）节点为递归边界，不断二分，形成一棵二叉树。

下一篇文章我们将介绍线段树的区间询问和单点修改，我们下次见。

dalao：拍砖ing