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

1. 特征

• 不一定是完全二叉樹

• 一定是平和二叉樹

• 葉子結點存儲的是實際的值，非葉子結點存的是自定義的內(nèi)容

2. 時間復雜度

3. 線段樹的圖解

4. 代碼

<?php /**  * content: 線段樹（區(qū)間樹）  * create: 2020-11-12  */  namespace HeapBundle;  use ArrayBundleBaseArray;  class SegmentTreeHeap {     /**      * 傳入的數(shù)組對象      * @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);     }      /**      * 構建線段樹      * @param int $treeIndex      * @param int $min      * @param int $max      * @throws Exception      */     public function build(int $treeIndex, int $min, int $max)     {         // 如果線段區(qū)間的最小值和最小值相同，則表示為葉子結點         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.示例

<?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視頻教程