共计 7216 个字符，预计需要花费 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-po…
扫码关注爱因诗贤
正文完