數據結構-PHP 線段樹的實現

2021-02-19 愛因詩賢
1.線段樹介紹

線段樹是基於區間的統計查詢，線段樹是一種 二叉搜索樹，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。使用線段樹可以快速的查找某一個節點在若干條線段中出現的次數，時間複雜度為O(logN)，線段樹是一顆 平衡二叉樹。

2.線段樹示意圖

如下圖所示，數組 E中，假設區間 0-9 一共 10 個元素，每個兒子節點區間元素的個數都是父親節點元素個數的一半，若出現 奇數 的情況，則右兒子元素區間比 左兒子 元素區間多一個：

Tips：如圖所示的中節點中區間指的是數組 E 的索引值。

3.線段樹需要空間分析

假設我們把 線段樹 看做是一顆 滿二叉樹，並且不考慮添加元素的情況（即區間固定），對於區間有 n 個元素的數組若 n=2^k(k是正整數) 則需要 2n 的空間，最差的情況是若 n=2^k+1 則需要 4n 的空間，如下圖所示，最下面一層沒有元素的節點使用 null 填充：

Tips: 若索引是從 i=0 開始的，左兒子 left(i) = 2*i+1，右兒子 right(i) = 2*i+2，parent(i) = (i-1)/2 取整；

對於滿二叉樹來說，需要的節點數如下：

若當 n=2^k+1 需要的的空間數：

Tips：對於區間有 n 個元素的數組若 n=2^k(k是正整數) 則需要 2n 的空間，最差的情況是若 n=2^k+1 則需要 4n 的空間就足夠了。

4.定義 SegmentTree 線段樹類

其中定義了 leftSon($i) 方法，表示求某個節點左兒子節點索引值的方法，rightSon($i) 表示求某個節點右兒子節點 索引值 的方法：

<?php


class SegmentTree
{
private $data = []; //用於存儲原始數組
private $tree = []; //用於存儲線段樹節點元素的值

/**
* 構造函數 初始化線段樹
* SegmentTree constructor.
* @param array $arr
*/
public function __construct(array $arr)
{
for ($i = 0; $i < count($arr); $i++) {
$this->data[$i] = $arr[$i];
}
//若是靜態語言需要開 4n 空間來表示 $this->tree
}

public function getSize()
{
return count($this->data);
}

public function get(int $index)
{
if ($index < 0 || $index >= count($this->data)) {
echo "索引錯誤";
exit;
}
return $this->data[$index];
}

/**
* 獲取某個節點兒子節點索引，若索引是從 i=0 開始的，左兒子 left(i) = 2*i+1
* @param $i
* @return int
*/
private function leftSon($i): int
{
return $i * 2 + 1;
}

/**
* 獲取某個節點右兒子節點索引，若索引是從 i=0 開始的，右兒子 left(i) = 2*i+2
* @param $i
* @return int
*/
private function rightSon($i): int
{
return $i * 2 + 2;
}
}

5.創建線段樹

接下來使用遞歸思想去 創建線段樹，下面給出遞歸函數 PHP 代碼：

if ($left == $right) {
$this->tree[$i] = $this->data[$left]; //處理遞歸到葉子節點時 並賦值最原始的 $data 對應的索引值
} else {
$leftSon = $this->leftSon($i); //左兒子索引
$rightSon = $this->rightSon($i); //右兒子索引
$mid = $left + ceil(($right - $left) / 2);//求區間中值
$this->buildSegmentTree($leftSon, $left, $mid - 1); //遞歸左兒子樹
$this->buildSegmentTree($rightSon, $mid, $right); //遞歸右兒子樹
$this->tree[$i] = $this->merge->operate($this->tree[$leftSon], $this->tree[$rightSon]); //這裡是根據業務來定節點需要存儲的元素
}

Tips：其中節點元素存儲的值需要根據業務來定，如上面代碼表示的是每個節點存儲的是 區間求和 的值，很顯然這種方式不靈活，用戶在實例化該類的時候可以傳入一個 merge 對象用於元素操作的。

6.節點元素計算規則

上述SegmentTree類中可以在 __construct() 方法中傳入一個 $merge 對象，$merge 中可以定義一個 operate() 方法計算得出節點元素值，如下：

<?php


class SegmentTree
{
private $data = [];
private $tree = [];
private $merge = null; //表示的是一個 節點操作的對象

/**
* 構造函數 初始化線段樹
* SegmentTree constructor.
* @param array $arr
*/
public function __construct(array $arr, $merge)
{
$this->merge = $merge;
for ($i = 0; $i < count($arr); $i++) {
$this->data[$i] = $arr[$i];
}
//若是靜態語言需要開 4n 空間來表示 $this->tree

//遞歸創建線段樹
$this->buildSegmentTree(0, 0, count($this->data) - 1);
}

private function buildSegmentTree(int $i, int $left, int $right)
{
if ($left == $right) {
$this->tree[$i] = $this->data[$left]; //處理遞歸到葉子節點時 並賦值最原始的 $data 對應的索引值
} else {
$leftSon = $this->leftSon($i); //左兒子索引
$rightSon = $this->rightSon($i); //右兒子索引
$mid = $left + ceil(($right - $left) / 2);//求區間中值
$this->buildSegmentTree($leftSon, $left, $mid - 1); //遞歸左兒子樹
$this->buildSegmentTree($rightSon, $mid, $right); //遞歸右兒子樹
$this->tree[$i] = $this->merge->operate($this->tree[$leftSon], $this->tree[$rightSon]); //這裡是根據業務來定節點需要存儲的元素
}
}

public function getSize()
{
return count($this->data);
}

public function get(int $index)
{
if ($index < 0 || $index >= count($this->data)) {
echo "索引錯誤";
exit;
}
return $this->data[$index];
}

/**
* 獲取某個節點兒子節點索引，若索引是從 i=0 開始的，左兒子 left(i) = 2*i+1
* @param $i
* @return int
*/
private function leftSon($i): int
{
return $i * 2 + 1;
}

/**
* 獲取某個節點右兒子節點索引，若索引是從 i=0 開始的，右兒子 left(i) = 2*i+2
* @param $i
* @return int
*/
private function rightSon($i): int
{
return $i * 2 + 2;
}
}

6.1 Merge 類定義

如下定義就可以很靈活的處理每個節點的計算規則：

class Merge{
public funcrion operate($left,$right){
//這裡可以定義需要操作的規則
return $left+$right; //如求平均值，這裡可以 return ($left+$right)/2;
}
}

7. 求和演示

若是各個線段區間存儲的是區間求和，則 Merge 類中的 operate() 方法返回是兩個元素的和，代碼如下：

<?php
require 'SegmentTree.php';

class Merge
{
public function operate($left, $right)
{
return $left + $right;
}
}

$merge = new Merge();

$arr = [0,1,2,3,4,5,6,7,8,9];
$merge = new Merge();
$segmentTree = new SegmentTree($arr,$merge);
print_r($segmentTree);

輸出如下：

此時線段樹的節點元素值示意圖如下：

8. 線段樹的區間查詢

這裡以查詢 [2-6] 區間為例，若要查詢區間 [2-6] 的求和需要根據區間來尋找需要求的值，示意圖如下：

PHP 代碼使用遞歸思想實現如下：

public function query($qleft, $qright)
{
if ($qleft < 0 || $qright >= count($this->data) || $qright < $qleft) {
echo "索引範圍錯誤";
exit;
}
return $this->recursionQuery(0, 0, count($this->data) - 1, $qleft, $qright);
}

/**
* 遞歸查詢區間
* @param $left 當前節點區間左端值
* @param $right 當前節點區間右端值
* @param $qleft 需要查詢的區間左端值
* @param $qright 需要查詢的區間右端值
*/
private function recursionQuery($i, $left, $right, $qleft, $qright)
{
$mid = $left + ceil(($right - $left) / 2);//求區間中值向上取整
//先處理滿足區間條件的情況
if ($qleft == $left && $qright == $right) { //查詢左右端和當前節點左右端重合
return $this->tree[$i];
} elseif ($qright < $mid) { //查詢左右端在中值左邊，那麼結果區間在左兒子樹
return $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $qright);
} elseif ($qleft >= $mid) { //查詢左右端在中值右邊，那麼結果區間在右兒子樹
return $this->recursionQuery($this->rightSon($i), $mid, $right, $qleft, $qright);
} else { //中值在查詢左右端中間 將區間分成兩邊，結果在左右兒子樹上都有
$leftSon = $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $mid - 1);
$righttSon = $this->recursionQuery($this->rightSon($i), $mid, $right, $mid, $qright);
return $this->merge->operate($leftSon, $righttSon);
}
}

輸出如下：

9.完整 PHP 代碼9.1 SegmentTree 類

<?php


class SegmentTree
{
private $data = [];
private $tree = [];
private $merge = null; //表示的是一個 節點操作的對象

/**
* 構造函數 初始化線段樹
* SegmentTree constructor.
* @param array $arr
*/
public function __construct(array $arr, $merge)
{
$this->merge = $merge;
for ($i = 0; $i < count($arr); $i++) {
$this->data[$i] = $arr[$i];
}
//若是靜態語言需要開 4n 空間來表示 $this->tree

//遞歸創建線段樹
$this->buildSegmentTree(0, 0, count($this->data) - 1);
}

public function query($qleft, $qright)
{
if ($qleft < 0 || $qright >= count($this->data) || $qright < $qleft) {
echo "索引範圍錯誤";
exit;
}
return $this->recursionQuery(0, 0, count($this->data) - 1, $qleft, $qright);
}

/**
* 遞歸查詢區間
* @param $left 當前節點區間左端值
* @param $right 當前節點區間右端值
* @param $qleft 需要查詢的區間左端值
* @param $qright 需要查詢的區間右端值
*/
private function recursionQuery($i, $left, $right, $qleft, $qright)
{
$mid = $left + ceil(($right - $left) / 2);//求區間中值向上取整
//先處理滿足區間條件的情況
if ($qleft == $left && $qright == $right) { //查詢左右端和當前節點左右端重合
return $this->tree[$i];
} elseif ($qright < $mid) { //查詢左右端在中值左邊，那麼結果區間在左兒子樹
return $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $qright);
} elseif ($qleft >= $mid) { //查詢左右端在中值右邊，那麼結果區間在右兒子樹
return $this->recursionQuery($this->rightSon($i), $mid, $right, $qleft, $qright);
} else { //中值在查詢左右端中間 將區間分成兩邊，結果在左右兒子樹上都有
$leftSon = $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $mid - 1);
$righttSon = $this->recursionQuery($this->rightSon($i), $mid, $right, $mid, $qright);
return $this->merge->operate($leftSon, $righttSon);
}
}

private function buildSegmentTree(int $i, int $left, int $right)
{
if ($left == $right) {
$this->tree[$i] = $this->data[$left]; //處理遞歸到葉子節點時 並賦值最原始的 $data 對應的索引值
} else {
$leftSon = $this->leftSon($i); //左兒子索引
$rightSon = $this->rightSon($i); //右兒子索引
$mid = $left + ceil(($right - $left) / 2);//求區間中值
$this->buildSegmentTree($leftSon, $left, $mid - 1); //遞歸左兒子樹
$this->buildSegmentTree($rightSon, $mid, $right); //遞歸右兒子樹
$this->tree[$i] = $this->merge->operate($this->tree[$leftSon], $this->tree[$rightSon]); //這裡是根據業務來定節點需要存儲的元素
}
}

public function getSize()
{
return count($this->data);
}

public function get(int $index)
{
if ($index < 0 || $index >= count($this->data)) {
echo "索引錯誤";
exit;
}
return $this->data[$index];
}

/**
* 獲取某個節點兒子節點索引，若索引是從 i=0 開始的，左兒子 left(i) = 2*i+1
* @param $i
* @return int
*/
private function leftSon($i): int
{
return $i * 2 + 1;
}

/**
* 獲取某個節點右兒子節點索引，若索引是從 i=0 開始的，右兒子 left(i) = 2*i+2
* @param $i
* @return int
*/
private function rightSon($i): int
{
return $i * 2 + 2;
}
}

9.2 輸出演示代碼

<?php
require 'SegmentTree.php';

class Merge
{
public function operate($left, $right)
{
return $left + $right;
}
}

$merge = new Merge();

$arr = [0,1,2,3,4,5,6,7,8,9];
$merge = new Merge();
$segmentTree = new SegmentTree($arr,$merge);

echo $segmentTree->query(2,6);

代碼倉庫 ：https://gitee.com/love-for-poetry/data-structure

掃碼關注愛因詩賢

相關焦點

  • 數據結構之php實現線段樹
    之前學習了二分搜索樹, 堆等一些數據結構. 今天我們一起學習一種新的樹形結構, 線段樹。
  • 數據結構:線段樹入門與實踐
    最近在刷題的時候，遇到一個涉及到線段樹的問題。之前沒接觸過，看了幾遍題解才看懂。這裡簡單介紹下入門的過程。高級數據結構，線段樹入門一、線段樹的基本思想 線段樹是一種常用來維護區間信息的數據結構，它適用於對區間內進行單點查詢、更新、求最值等操作，且時間複雜度能控制到 O(logN)。
  • 什麼是線段樹?
    一、概念解析 這次來介紹一個數據結構 - 線段樹。在平時刷題或是工作中，經常會遇到這麼一個問題，「給定一個數組，求出數組某段區間的一些性質」。比如給定一個數組 [5,2,6,1,-4,0,9,2]，讓你求出區間 [1,4] 上所有元素的和，在這個例子中，答案是 2 + 6 + 1 + (-4) = 5。
  • 數據結構-PHP 哈希表(Hash Table)的實現
    2.4 用 PHP 代碼實現的 HashCode 類下面這個類可以實現輸入一個字符串，然後返回一個正整數的哈希值：<?4.演示哈希值輸出下面給出 output_hash_table.php 代碼：<?
  • [洛穀日報第46期]線段樹的擴展之淺談zkw線段樹
    （加法乘法混合處理）例如洛谷P3373）2 zkw線段樹的實現我們觀察一下遞歸式線段樹的代碼，很容易就會發現：無論是建樹、修改還是查詢，都是自頂向下的。）內的數據如果我們想要查詢[0,m]範圍內（ 0\leq m\leq n ）的呢？
  • GGTalk 中有哪些知識 - 線段樹基礎與 RMQ 問題
    所以我們的出發點是通過一種優質的數據結構，將查詢複雜度降低成 O(logn) 或者 O(1)。由於查詢次數是強需求，不是算法層面上可以優化的，所以在查詢上的效率是我們主要解決的問題。為了解決查詢問題，這一篇文章我們引入線段樹（Binary Indexed Tree）來優化 RMQ 問題的查詢操作。
  • 線段樹,看這一篇就夠了
    定義線段樹（segment tree），顧名思義， 是用來存放給定區間（segment, or interval）內對應信息的一種數據結構。與樹狀數組（binary indexed tree）相似，線段樹也用來處理數組相應的區間查詢（range query）和元素更新（update）操作。
  • 圖解:什麼是線段樹?
    簡介 線段樹是在算法競賽中常用來維護區間信息的數據結構，同時，線段樹的理解難度較樹狀數組低（當然是在理解遞歸的前提下）。線段樹的結構與建樹 線段樹將每個長度不為1的區間劃分為左右兩個區間，並遞歸處理，通過合併左右兩個區間的信息來求得該區間的信息。對於例題來說，我們想要得到的是指定區間裡數的和，那麼，我們要求的區間信息便是該區間數的和，合併左右兩個區間的信息即是將兩個區間的值進行相加。
  • 五分鐘學算法:什麼是線段樹?
    因此我們需要一個數據結構能夠幫助我們解決大部分數組的區間問題，而且時間複雜度要儘可能的低。這也就是今天的主題 - 線段樹，首先要說明一點的是，線段樹也是二叉樹，只是它的節點裡面含有區間的信息。線段線段樹有三個基本的操作，分別是 構建線段樹(build)、區間查找(query)、還有就是 修改(modify)，假設我們現在需要解決的問題是 「求區間上的最大值」，例子還是之前的例子，一起來看看怎麼實現這些操作。
  • [洛穀日報第4期]淺談線段樹——Segment Tree
    一、簡介線段樹ps: _此處以詢問區間和為例。實際上線段樹可以處理很多符合結合律的操作。（比如說加法，a[1]+a[2]+a[3]+a[4]=(a[1]+a[2])+(a[3]+a[4])）線段樹之所以稱為「樹」，是因為其具有樹的結構特性。線段樹由於本身是專門用來處理區間問題的（包括RMQ、RSQ問題等。
  • PHP+MySQL實現對一段時間內每天數據統計優化操作實例
    關注我喲小編 隔天推送php教程，php技巧，php視頻教程，MySQL，筆試題等諸多優質內容，最接地氣、重服務的本地微信平臺！關注我們妥妥沒錯！（商務合作聯繫QQ號：2230304070）http://www.jb51.net/article/136685.htm這篇文章主要介紹了PHP+MySQL實現對一段時間內每天數據統計優化操作,結合具體實例形式分析了php針對mysql查詢統計相關優化操作技巧
  • PHP 實現簡單的 MVC 框架
    項目名稱：【PHP 實現簡單的 MVC 框架】項目簡介：該項目課程使用 PHP 實現一個簡單的 MVC 框架，包含模型、視圖、控制器以及模板解析等部分。通過項目了解MVC框架的基本原理和運行流程，學習面向對象編程和MVC設計模式，並學習開發中的一些注意事項。
  • php框架開發:實現最簡單的MVC框架實例教程
    這篇文章主要介紹了php實現最簡單的MVC框架實例教程,講述了MVC框架的運行原理及簡單實現方法，具有不錯的參考借鑑價值,
  • 數據結構與算法?看這篇就夠了!!!
    有一種對所有程式設計師無一例外的剛需 —— 算法與數據結構日常增刪改查 + 粘貼複製 + 搜尋引擎可以實現很多東西。同樣，這樣也是沒有任何競爭力的。我們只可以粘貼複製相似度極高的功能，稍複雜的邏輯沒有任何辦法。語言有很多，開發框架更是日新月異3個月不學就落後。
  • 算法與數據結構?看這篇就夠了
    有一種對所有程式設計師無一例外的剛需 —— 算法與數據結構日常增刪改查 + 粘貼複製 + 搜尋引擎可以實現很多東西。同樣，這樣也是沒有任何競爭力的。我們只可以粘貼複製相似度極高的功能，稍複雜的邏輯沒有任何辦法。語言有很多，開發框架更是日新月異3個月不學就落後。
  • 簡述MVC思想與PHP如何實現MVC
    首頁 > 語言 > 關鍵詞 > php最新資訊 > 正文 簡述MVC思想與PHP如何實現MVC
  • 給球上色(線段樹+離散化) - HDU 1199
    使用STL離散化大大減少了代碼量且結構相當清晰。本題涉及離散化和線段樹的應用，線段樹採用數組實現，新手看起來較為吃力，可以多多琢磨實現思路。 Sample Input3 1 4 w 8 11 w 3 5 b Sample Output8 11解題思路：1、輸入區間，離散化區間2、建立線段樹，然後通過線段樹對每個節點著色3、依次計算連續區間的顏色原始碼：g++
  • PHP使用Curl實現模擬登錄及抓取數據功能示例
    關注我喲小編 隔天推送php教程，php技巧，php視頻教程，MySQL，筆試題等諸多優質內容，最接地氣、重服務的本地微信平臺！關注我們妥妥沒錯！（商務合作聯繫QQ號：2230304070）http://www.jb51.net/article/139048.htm使用PHP的Curl擴展庫可以模擬實現登錄，並抓取一些需要用戶帳號登錄以後才能查看的數據。具體實現的流程如下：1.
  • 如何利用PHP-FPM實現open_basedir繞過
    伺服器在認為這是一個CGI請求時，會調用相關CGI程序，並通過環境變量和標準輸出將數據傳送給CGI程序，CGI程序處理完數據，生成html，然後再通過標準輸出將內容返回給伺服器，伺服器再將內容交給用戶瀏覽器，CGI進程退出。
  • PHP empty()和is_array()實現源碼分析
    於是乎，我去看了兩者的源碼實現。is_array()的實現is_array()是php內置函數，通過擴展方式實現的。打開php源碼，ext/standard/type.c文件，打開後看到其實現：PHP_FUNCTION(is_array){    php_is_type(INTERNAL_FUNCTION_PARAM_PASSTHRU, IS_ARRAY);}可見是調用php_is_type函數實現。