這篇文章主要講解了“PHP怎么實(shí)現(xiàn)線段樹”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“PHP怎么實(shí)現(xiàn)線段樹”吧！

為巴中等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及巴中網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站制作、巴中網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個(gè)區(qū)間劃分成一些單元區(qū)間，每個(gè)單元區(qū)間對(duì)應(yīng)線段樹中的一個(gè)葉結(jié)點(diǎn)。下面就由小編給大家分享一下php實(shí)現(xiàn)線段樹的方法，有需要的可以參考一下。

1. 特征

• 不一定是完全二叉樹

• 一定是平和二叉樹

• 葉子結(jié)點(diǎn)存儲(chǔ)的是實(shí)際的值，非葉子結(jié)點(diǎn)存的是自定義的內(nèi)容

2. 時(shí)間復(fù)雜度

操作	時(shí)間復(fù)雜度
查詢	O(logn)

3. 線段樹的圖解

4. 代碼

<?php
/**
 * content: 線段樹（區(qū)間樹）
 * create: 2020-11-12
 */

namespace HeapBundle;

use ArrayBundle\BaseArray;

class SegmentTreeHeap
{
    /**
     * 傳入的數(shù)組對(duì)象
     * @var BaseArray 
     */
    protected $array;

    /**
     * 數(shù)組
     * @var array 
     */
    protected $tree = [];

    public function __construct(BaseArray $array)
    {
        $this->array = $array;
        $this->build(0, 0, $this->array->getSize() - 1);
    }

    /**
     * 構(gòu)建線段樹
     * @param int $treeIndex
     * @param int $min
     * @param int $max
     * @throws \Exception
     */
    public function build(int $treeIndex, int $min, int $max)
    {
        // 如果線段區(qū)間的最小值和最小值相同，則表示為葉子結(jié)點(diǎn)
        if ($min == $max) {
            $this->tree[$treeIndex] = $this->array->get($max);
            return;
        }

        // 四舍五入取中間值  最大值減最小值然后除以2拿到中間值，并加上最小值
        $mid = floor(($max - $min) / 2) + $min;

        // 獲取左兒子的索引值，并遞歸往下構(gòu)建
        $leftIndex = $this->leftChildIndex($treeIndex);
        $this->build($leftIndex, $min, $mid);

        // 獲取右兒子的索引值，并遞歸往下構(gòu)建
        $rightIndex = $this->rightChildIndex($treeIndex);
        $this->build($rightIndex, $mid + 1, $max);

        // 非葉子結(jié)點(diǎn)的值保留的是它下面所有結(jié)點(diǎn)的相加值, 這里可以改為它下面結(jié)點(diǎn)的總和值
        $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('父結(jié)點(diǎn)的索引不能小于0');
        return $parentIndex * 2 + 1;
    }

    /**
     * 獲取右兒子索引
     * @param int $parentIndex
     * @return int
     * @throws \Exception
     */
    public function rightChildIndex(int $parentIndex): int
    {
        if ($parentIndex < 0) throw new \Exception('父結(jié)點(diǎn)的索引不能小于0');
        return $parentIndex * 2 + 2;
    }
}

5.示例

<?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怎么實(shí)現(xiàn)線段樹”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)PHP怎么實(shí)現(xiàn)線段樹這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

分享題目：PHP怎么實(shí)現(xiàn)線段樹
分享地址：http://chinadenli.net/article40/gdgpho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、面包屑導(dǎo)航、網(wǎng)站改版、定制開發(fā)、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)