这篇文章主要讲解了“PHP怎么实现线段树”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“PHP怎么实现线段树”吧！
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。下面就由小编给大家分享一下php实现线段树的方法，有需要的可以参考一下。
| 操作 | 时间复杂度 |
|---|---|
| 查询 | O(logn) |
计算
安全
数据库
网络和加速
企业服务
<?php
/**
* content: 线段树（区间树）
* create: 2020-11-12
*/
namespace HeapBundle;
use ArrayBundle\BaseArray;
class SegmentTreeHeap
{
/**
* 传入的数组对象
* @var BaseArray
*/
protected $array;
/**
* 数组
* @var array
*/
protected $tree = [];
public function __construct(BaseArray $array)
{
$this->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;
}
}<?php
require_once __DIR__ . '/../../vendor/autoload.php';
$array = new ArrayBundleBaseArray();
for ($i = 0; $i < 10; $i++) {
$array->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怎么实现线段树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
