1。线段树介绍线段树是一种基于区间的统计查询。线段树是一种二叉搜索树，它将一个区间划分为若干个单位区间，每个单位区间对应线段树中的一个叶子节点。使用线段树可以快速求出某个节点在若干条线段中出现的次数，时间复杂度为O(logN)，线段树是一棵平衡二叉树。2、线段树的示意图如下图所示。在数组E中，假设0-9区间共有10个元素，每个子节点区间的元素个数是父节点元素个数的一半。如果有奇数，则右子的元素区间比左子的元素区间多1：小贴士：图中中间节点的中间区间指的是数组E的索引值.3.线段树需要空间分析。假设我们把线段树看成一棵满二叉树，不考虑添加元素的情况（即区间固定）。对于区间有n个元素的数组，如果n=2^k（k为正整数）需要2n个空格，最坏的情况是如果n=2^k+1需要4n个空格，如下图，底层没有元素的节点用null填充：提示：如果索引是从i=0开始，左子left(i)=2*i+1，右子right(i)=2*i+2,parent(i)=(i-1)/2四舍五入；对于满二叉树，一般来说，需要的节点个数如下：如果n=2^k+1需要的空格个数：Tips：对于区间有n个元素的数组，如果n=2^k(k是一个正整数），需要2n个空格，最坏的情况是如果n=2^k+1，4n个空格就够了。4.定义SegmentTree线段树类，其中定义了leftSon($i)方法，意思是找一个节点的左子节点的索引值的方法，rightSon($i)意思是找左子节点的索引值的方法某节点右子节点索引值：data[$i]=$arr[$我];}//对于静态语言，需要开4n个空格来表示$this->tree}publicfunctiongetSize(){returncount($this->data);}publicfunctionget(int$index){if($index<0||$index>=count($this->data)){echo"索引错误";出口;}返回$this->data[$index];}/***获取一个节点的子节点的索引，如果索引从i=0开始，左子left(i)=2*i+1*@param$i*@returnint*/privatefunctionleftSon($i):int{返回$i*2+1;}/***获取一个节点的右孩子的索引，如果索引从i=0开始，则为右孩子left(i)=2*i+2*@param$i*@returnint*/privatefunctionrightSon($i):int{return$i*2+2;}}5.创建线段树然后使用递归思路是创建线段树，递归函数PHP代码如下：if($left==$right){$this->tree[$i]=$this->data[$left];//处理递归到叶子节点，将最原始的$data对应的索引值赋值}else{$leftSon=$this->leftSon($i);//左子索引$rightSon=$this->rightSon($i);//右子索引$mid=$left+ceil(($right-$left)/2);//求区间的中值$this->buildSegmentTree($leftSon,$left,$mid-1);//递归左子树$this->buildSegmentTree($rightSon,$mid,$right);//递归右子树$this->tree[$i]=$this->merge->operate($this->tree[$leftSon],$this->tree[$rightSon]);//这里是根据业务来确定节点中需要存储的元素}小提示：节点元素中存储的值需要根据业务来确定，比如上面的代码代表每个节点存储的是什么是区间之和的值。显然，这种方法并不灵活。在实例化该类时，用户可以传入一个合并对象进行元素操作。6、节点元素计算规则在上面的SegmentTree类中，可以在__construct()方法中传入一个$merge对象，在$merge中定义一个operate()方法来计算节点元素值，如下：merge=$merge;对于($i=0;$idata[$i]=$arr[$i];}//如果是静态语言，需要开4n个空格来表示$this->tree//递归创建线段树$this->buildSegmentTree(0,0,count($this->data)-1);}privatefunctionbuildSegmentTree(int$i,int$left,int$right){if($left==$right){$this->tree[$i]=$this->data[$left];//处理递归到叶子节点，将最原始的$data对应的索引值赋值}else{$leftSon=$this->leftSon($i);//左子索引$rightSon=$this->rightSon($i);//右子索引$mid=$left+ceil(($right-$left)/2);//求区间的中值$this->buildSegmentTree($leftSon,$left,$mid-1);//递归左子树$this->buildSegmentTree($rightSon,$mid,$right);//递归右子树$this->tree[$i]=$this->merge->operate($this->tree[$leftSon],$this->tree[$rightSon]);//这里是根据业务确定节点需要存储的元素}}publicfunctiongetSize(){returncount($this->data);}publicfunctionget(int$index){if($index<0||$index>=count($this->data)){echo"索引错误";出口;}返回$this->data[$index];}/***获取一个节点的子节点Index，如果index从i=0开始，则leftsonleft(i)=2*i+1*@param$i*@returnint*/privatefunctionleftSon($i):int{返回$i*2+1;}/***获取一个节点的右孩子节点的索引，如果索引从i=0开始，则右孩子left(i)=2*i+2*@param$i*@returnint*/私有函数rightSon($i):int{return$i*2+2;}}6.1合并类定义每个节点的计算规则可以通过如下定义灵活处理：classMerge{publicfuncrionoperate($left,$right){//这里可以定义需要操作的规则return$left+$right;//比如求平均，这里可以return($left+$right)/2;}}7.求和演示如果每条线段区间都存储区间求和，则Merge类中的operate()方法返回两个元素的求和，代码如下：=count($this->data)||$qright<$qleft){echo"索引范围错误";出口;}返回$this->recursionQuery(0,0,count($this->data)-1,$qleft,$qright);}/***递归查询区间*@param$left当前节点区间左端值*@param$right当前节点区间右端值*@param$qleft待查询区间左端值*@param$qright待查询区间右端值*/privatefunctionrecursionQuery($i,$left,$right,$qleft,$qright){$mid=$left+ceil(($right-$left)/2);//计算区间的中值并向上取整//先处理满足区间条件的情况if($qleft==$left&&$qright==$right){//查询左右两端是否与当前节点的左右两端重合return$this->tree[$i];}elseif($qright<$mid){//查询的左右两端在中位数左边，则结果区间在左子树中return$this->recursionQuery($this->leftSon($i),$left,$mid-1,$qleft,$qright);}elseif($qleft>=$mid){//查询的左右两端都在中位数的右边，那么结果区间在右子树中return$this->recursionQuery($this->rightSon($i),$mid,$right,$qleft,$qright);}else{//中位数将query左右两端的区间除以两边，结果有$leftSon=$this->recursionQuery($this->leftSon($i),$left,$mid-1,$qleft,$mid-1);$righttSon=$this->recursionQuery($this->rightSon($i),$mid,$right,$mid,$qright);返回$this->merge->operate($leftSon,$righttSon);}}输出结果如下：9.完整的PHP代码9.1SegmentTree类merge=$merge;对于($i=0;$idata[$i]=$arr[$i];}//如果是静态语言，需要开4n个空间表示$this->tree//递归创建线段树$this->buildSegmentTree(0,0,count($this->data)-1);}publicfunctionquery($qleft,$qright){if($qleft<0||$qright>=count($this->data)||$qright<$qleft){echo"索引范围错误";出口;}返回$this->recursionQuery(0,0,count($this->data)-1,$qleft,$qright);}/***递归查询区间*@param$left当前节点区间左端值*@param$right当前节点区间右端值*@param$qleft待查询区间左端值*@param$qright待查询区间右端值*/privatefunctionrecursionQuery($i,$left,$right,$qleft,$qright){$mid=$left+ceil(($right-$left)/2);//求区间的中值并向上取整//先处理满足区间条件的情况if($qleft==$left&&$qright==$right){//查询左右两端与当前节点的左右两端重合return$this->tree[$i];}elseif($qright<$mid){//查询的左右两端在中位数左边，则结果区间在左子树中return$this->recursionQuery($this->leftSon($i),$left,$mid-1,$qleft,$qright);}elseif($qleft>=$mid){//查询的左右两端在中位数的右边，则结果区间在右子树中return$this->recursionQuery($this->rightSon($i),$mid,$right,$qleft,$qright);}else{//中位数是在query的左右两端之间分成两侧，结果为$leftSon=$this->recursionQuery($this->leftSon($i),$left,$mid-1,$qleft,$mid-1);$righttSon=$this->recursionQuery($this->rightSon($i),$mid,$right,$mid,$qright);返回$this->merge->op率（$leftSon，$righttSon）；}}私有函数buildSegmentTree(int$i,int$left,int$right){if($left==$right){$this->tree[$i]=$this->data[$left];//处理递归到叶子节点，将最原始的$data对应的索引值赋值}else{$leftSon=$this->leftSon($i);//左子索引$rightSon=$this->rightSon($i);//右子索引$mid=$left+ceil(($right-$left)/2);//求区间的中位数$this->buildSegmentTree($leftSon,$left,$mid-1);//递归左子树$this->buildSegmentTree($rightSon,$mid,$right);//递归右子树$this->tree[$i]=$this->merge->operate($this->tree[$leftSon],$this->tree[$rightSon]);//这里是根据业务要存入节点的元素}}publicfunctiongetSize(){returncount($this->data);}publicfunctionget(int$index){if($index<0||$index>=count($this->data)){echo"索引错误";出口;}返回$this->数据[$索引];}/***获取节点的子节点的索引。如果索引从i=0开始，左孩子left(i)=2*i+1*@param$i*@returnint*/privatefunctionleftSon($i):int{return$i*2+1;}/***获取一个节点的右子节点的索引，如果索引从i=0开始，则右子left(i)=2*i+2*@param$i*@returnint*/私有函数rightSon($i):int{return$i*2+2;}}9.2输出演示代码query(2,6);代码仓库：https://gitee。com/love-for-po...扫描二维码关注爱因世贤
