PHP如何实现线段树

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

1. 特征

• 不一定是完全二叉树

• 一定是平和二叉树

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

2. 时间复杂度

3. 线段树的图解

云商商城系统

云商商城系统，即云商未来商城系统，云商商城系统提供完整的电子商务解决方案。云商商城系统集CMS、B2C、B2B2C、B2B、C2B、SNS用户社区于一体，包括网站商城、微信商城、手机商城等多种交易模式，支持实现不同模式的O2O电子商务平台。为企业树立企业品牌形象，实现独立网络推广，批发、零售，供应商加盟，并充分结合网站SEO、微博、APP，微信等移动客户端多渠道网络营销手段，实现线上线下统一管理，

下载

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视频教程