PHP怎么实现线段树
这篇文章主要讲解了“PHP怎么实现线段树”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“PHP怎么实现线段树”吧!
为巴中等地区用户提供了全套网页设计制作服务,及巴中网站建设行业解决方案。主营业务为网站设计制作、成都网站制作、巴中网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。下面就由小编给大家分享一下php实现线段树的方法,有需要的可以参考一下。
1. 特征
不一定是完全二叉树
一定是平和二叉树
叶子结点存储的是实际的值,非叶子结点存的是自定义的内容
2. 时间复杂度
操作 | 时间复杂度 |
---|---|
查询 | O(logn) |
3. 线段树的图解
4. 代码
array = $array; $this->build(0, 0, $this->array->getSize() - 1); } /** * 构建线段树 * @param int $treeIndex * @param int $min * @param int $max * @throws \Exception */ public function build(int $treeIndex, int $min, int $max) { // 如果线段区间的最小值和最小值相同,则表示为叶子结点 if ($min == $max) { $this->tree[$treeIndex] = $this->array->get($max); return; } // 四舍五入取中间值 最大值减最小值然后除以2拿到中间值,并加上最小值 $mid = floor(($max - $min) / 2) + $min; // 获取左儿子的索引值,并递归往下构建 $leftIndex = $this->leftChildIndex($treeIndex); $this->build($leftIndex, $min, $mid); // 获取右儿子的索引值,并递归往下构建 $rightIndex = $this->rightChildIndex($treeIndex); $this->build($rightIndex, $mid + 1, $max); // 非叶子结点的值保留的是它下面所有结点的相加值, 这里可以改为它下面结点的总和值 $this->tree[$treeIndex] = $this->tree[$leftIndex] . '+' . $this->tree[$rightIndex]; } /** * 打印线段树 */ public function varDump() { ksort($this->tree); print_r($this->tree); } /** * 获取线段树的长度 * @return int */ public function getSize(): int { return count($this->tree); } /** * 获取左儿子索引 * @param int $parentIndex * @return int * @throws \Exception */ public function leftChildIndex(int $parentIndex): int { if ($parentIndex < 0) throw new \Exception('父结点的索引不能小于0'); return $parentIndex * 2 + 1; } /** * 获取右儿子索引 * @param int $parentIndex * @return int * @throws \Exception */ public function rightChildIndex(int $parentIndex): int { if ($parentIndex < 0) throw new \Exception('父结点的索引不能小于0'); return $parentIndex * 2 + 2; } }
5.示例
addLast($i + 10); } $heap = new HeapBundleSegmentTreeHeap($array); $heap->varDump();
Array ( [0] => 10+11+12+13+14+15+16+17+18+19 [1] => 10+11+12+13+14 [2] => 15+16+17+18+19 [3] => 10+11+12 [4] => 13+14 [5] => 15+16+17 [6] => 18+19 [7] => 10+11 [8] => 12 [9] => 13 [10] => 14 [11] => 15+16 [12] => 17 [13] => 18 [14] => 19 [15] => 10 [16] => 11 [23] => 15 [24] => 16 )
感谢各位的阅读,以上就是“PHP怎么实现线段树”的内容了,经过本文的学习后,相信大家对PHP怎么实现线段树这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
网页题目:PHP怎么实现线段树
网页路径:http://myzitong.com/article/gdgpho.html