PHP怎么实现线段树

这篇文章主要讲解了“PHP怎么实现线段树”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“PHP怎么实现线段树”吧！

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。下面就由小编给大家分享一下php实现线段树的方法，有需要的可以参考一下。

1. 特征

• 不一定是完全二叉树

• 一定是平和二叉树

• 叶子结点存储的是实际的值，非叶子结点存的是自定义的内容

2. 时间复杂度

3. 线段树的图解

4. 代码

<?phpnamespace HeapBundle;use ArrayBundle\BaseArray;class SegmentTreeHeap{        protected $array;        protected $tree = [];    public function __construct(BaseArray $array)    {        $this->array = $array;        $this->build(0, 0, $this->array->getSize() - 1);    }        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);    }        public function getSize(): int    {        return count($this->tree);    }        public function leftChildIndex(int $parentIndex): int    {        if ($parentIndex < 0) throw new \Exception('父结点的索引不能小于0');        return $parentIndex * 2 + 1;    }        public function rightChildIndex(int $parentIndex): int    {        if ($parentIndex < 0) throw new \Exception('父结点的索引不能小于0');        return $parentIndex * 2 + 2;    }}

5.示例

<?phprequire_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怎么实现线段树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！