php開發(fā)手冊(cè)線段樹是為區(qū)間更新和區(qū)間查詢而生的數(shù)據(jù)結(jié)構(gòu)，旨在快速解決區(qū)間問(wèn)題力軟開發(fā)框架的開發(fā)手冊(cè)
2022-03-25
線段樹是一種用于區(qū)間更新和區(qū)間查詢的數(shù)據(jù)結(jié)構(gòu)，旨在快速解決區(qū)間問(wèn)題。
一般來(lái)說(shuō)，線段樹不會(huì)添加節(jié)點(diǎn)，也不支持動(dòng)態(tài)添加節(jié)點(diǎn)。段樹也是二叉樹的一種，但它的節(jié)點(diǎn)是由一個(gè)區(qū)間定義的。葉節(jié)點(diǎn)是具有單個(gè)間隔的節(jié)點(diǎn)。所以線段樹本質(zhì)上是一棵區(qū)間樹。
我們?cè)谒阉鞯臅r(shí)候，只需要找出哪些子區(qū)間構(gòu)成了結(jié)果區(qū)間。
實(shí)現(xiàn)代碼
先定義基本結(jié)構(gòu)
public class SegmentTree {
private Integer value;
private Integer maxValue;
private Integer l;
private Integer r;
private SegmentTree leftChild;
private SegmentTree rightChild;
}
復(fù)制代碼l 和 r 用于唯一地表征這個(gè)區(qū)間。那么其他的內(nèi)容就和標(biāo)準(zhǔn)的二叉樹沒(méi)什么區(qū)別了。
???
建樹過(guò)程
和二叉樹構(gòu)造沒(méi)什么區(qū)別，我們這里使用的是前序構(gòu)造方法。代碼顯示如下：
public static SegmentTree buildTree(int left, int right, int[] value) {
if (left > right) {
return null;
}
SegmentTree node = new SegmentTree();
node.setValue(value[left]);
node.setL(left);
node.setR(right);
if (left == right) {
// TODO: 2022/1/17 退出條件
node.setMaxValue(node.getValue());
return node;
}
int mid = (left + right) >>> 1;
node.setLeftChild(buildTree(left, mid, value));
node.setRightChild(buildTree(mid + 1, right, value));
if (Objects.isNull(node.getLeftChild())) {
if (Objects.isNull(node.getRightChild())) {
node.setMaxValue(node.getValue());
} else {
node.setMaxValue(node.getRightChild().getMaxValue());
}
} else {
if (Objects.isNull(node.getRightChild())) {
node.setMaxValue(node.getLeftChild().getMaxValue());
} else {
node.setMaxValue(Math.max(node.getLeftChild().getMaxValue(),
node.getRightChild().getMaxValue()));
}
}
return node;
}
復(fù)制代碼可以看出，這里葉子節(jié)點(diǎn)的判斷條件是 left == 。在其他方面，它與二叉樹沒(méi)有什么不同。
???
查詢區(qū)間最大值
public static Integer getMaxValue(SegmentTree segmentTree, int left, int right) {
if (Objects.isNull(segmentTree)) return null;
if (segmentTree.getL() == left && segmentTree.getR() == right) {
System.out.println("獲取了區(qū)間 [" + left + "," + right + "] 的最大值" + segmentTree.getMaxValue());
return segmentTree.getMaxValue();
}
int segMid = (segmentTree.getL() + segmentTree.getR()) >>> 1;
if (segMid < left) {
return getMaxValue(segmentTree.getRightChild(), left, right);
}
if (segMid >= right) {
return getMaxValue(segmentTree.getLeftChild(), left, right);
}
// TODO: 2022/1/17 左半邊答案
Integer leftMax = getMaxValue(segmentTree.getLeftChild(), left, segMid);
Integer rightMax = getMaxValue(segmentTree.getRightChild(), segMid + 1, right);
if (Objects.isNull(leftMax)) {
if (Objects.isNull(rightMax)) {
return -100000;
} else {
return rightMax;
}
} else {
if (Objects.isNull(rightMax)) {
return leftMax;
} else {
return Math.max(leftMax, rightMax);
}
}
}
復(fù)制代碼從上面的代碼分析，設(shè)置當(dāng)前節(jié)點(diǎn)的區(qū)間為[L,R]，那么對(duì)于區(qū)間[l,r]的最大值，需要進(jìn)行分類討論。如果LR區(qū)間的中點(diǎn)Mid在lr區(qū)間的左側(cè)，則max(lr) = max( , l, r); 如果LR區(qū)間的中點(diǎn)在lr區(qū)間的右側(cè)，則max(lr) = max(left , l, r); 如果 Mid 在 lr 區(qū)間內(nèi)，max(lr) = max(left , l, mid) 和 max( , mid+1, r) 中的較大者。
???
我們來(lái)看看測(cè)試用例和運(yùn)行結(jié)果：
public static void main(String[] args) {
int[] a = new int[]{2, 5, 4, 7, 6, 0, 1, -1, 2, 3, 6, 7, 0, 2, 9, 8, 5, 4, 7, 2};
SegmentTree segmentTree = buildTree(0, a.length - 1, a);
System.out.println(getMaxValue(segmentTree, 0, 16));
}
復(fù)制代碼結(jié)果如下
得到區(qū)間[0,9]的最大值 7 得到區(qū)間[10,14]的最大值 得到區(qū)間[15,16]的最大值 8 9
得到間隔和
現(xiàn)在需要改變?cè)瓉?lái)的建樹過(guò)程。首先php開發(fā)手冊(cè)，將 sum 字段添加到基礎(chǔ)架構(gòu)
public class SegmentTree {
private Integer value;
private Integer maxValue;
private Integer sum;
private Integer l;
private Integer r;
private SegmentTree leftChild;
private SegmentTree rightChild;
}
復(fù)制代碼然后在構(gòu)造方法中，加上sum的維護(hù)
public static SegmentTree buildTree(int left, int right, int[] value) {
if (left > right) {
return null;
}
SegmentTree node = new SegmentTree();
node.setValue(value[left]);
node.setL(left);
node.setR(right);
if (left == right) {
// TODO: 2022/1/17 退出條件
node.setMaxValue(node.getValue());
node.setSum(node.getValue());
return node;
}
int mid = (left + right) >>> 1;
node.setLeftChild(buildTree(left, mid, value));
node.setRightChild(buildTree(mid + 1, right, value));
if (Objects.isNull(node.getLeftChild())) {
if (Objects.isNull(node.getRightChild())) {
node.setMaxValue(node.getValue());
node.setSum(node.getValue());
} else {
node.setMaxValue(node.getRightChild().getMaxValue());
node.setSum(node.getRightChild().getSum());
}
} else {
if (Objects.isNull(node.getRightChild())) {
node.setMaxValue(node.getLeftChild().getMaxValue());
node.setSum(node.getLeftChild().getSum());
} else {
node.setMaxValue(Math.max(node.getLeftChild().getMaxValue(),
node.getRightChild().getMaxValue()));
node.setSum(node.getLeftChild().getSum() + node.getRightChild().getSum());
}
}
return node;
}
復(fù)制代碼然后得到總和
public static Integer getSum(SegmentTree segmentTree, int left, int right) {
if (Objects.isNull(segmentTree)) return null;
if (segmentTree.getL() == left && segmentTree.getR() == right) {
System.out.println("獲取了區(qū)間 [" + left + "," + right + "] 的和" + segmentTree.getSum());
return segmentTree.getSum();
}
int segMid = (segmentTree.getL() + segmentTree.getR()) >>> 1;
if (segMid < left) {
return getSum(segmentTree.getRightChild(), left, right);
}
if (segMid >= right) {
return getSum(segmentTree.getLeftChild(), left, right);
}
// TODO: 2022/1/17 左半邊答案
Integer leftSum = getSum(segmentTree.getLeftChild(), left, segMid);
Integer rightSum = getSum(segmentTree.getRightChild(), segMid + 1, right);
if (Objects.isNull(leftSum)) {
if (Objects.isNull(rightSum)) {
return segmentTree.getSum();
} else {
return rightSum;
}
} else {
if (Objects.isNull(rightSum)) {
return leftSum;
} else {
return leftSum + rightSum;
}
}
}
復(fù)制代碼測(cè)試過(guò)程和結(jié)果如下：
public static void main(String[] args) {
int[] a = new int[]{2, 5, 4, 7, 6, 0, 1, -1, 2, 3, 6, 7, 0, 2, 9, 8, 5, 4, 7, 2};
SegmentTree segmentTree = buildTree(0, a.length - 1, a);
System.out.println(getSum(segmentTree,0,3));
}
復(fù)制代碼得到區(qū)間[0,2]之和 11 得到區(qū)間[3,3]之和 7 18
單點(diǎn)更新
/**
* 這里的left == right
*
* @param segmentTree
* @param left
* @param right
* @param value
*/
public static void update(SegmentTree segmentTree, int left, int right, int value) {
if (segmentTree.getL() == left && segmentTree.getR() == right) {
segmentTree.setValue(value);
segmentTree.setMaxValue(value);
segmentTree.setSum(value);
return;
}
int mid = (segmentTree.getL() + segmentTree.getR()) >>> 1;
if (mid >= left) {
update(segmentTree.getLeftChild(), left, right, value);
}
if (mid < left) {
update(segmentTree.getRightChild(), left, right, value);
}
segmentTree.setMaxValue(Math.max(segmentTree.getLeftChild().getMaxValue(),segmentTree.getRightChild().getMaxValue()));
segmentTree.setSum(segmentTree.getLeftChild().getSum() + segmentTree.getRightChild().getSum());
}
復(fù)制代碼更新時(shí)采用遞歸的方式從左右節(jié)點(diǎn)不斷尋找需要更新的區(qū)間，同時(shí)更新上級(jí)節(jié)點(diǎn)的最新值。
總結(jié)
您可以根據(jù)需要擴(kuò)展它。請(qǐng)記住小程序開發(fā)，線段樹是以區(qū)間為維度的二叉樹，或以二維維度為特征的二叉樹。普通的二叉樹只有一維。這樣php開發(fā)手冊(cè)，我們?cè)谟?jì)算多維值的時(shí)候網(wǎng)站優(yōu)化，其實(shí)可以這樣構(gòu)造線段樹（二維樹、三維樹、n維樹）。不管樹的維數(shù)多少，找到結(jié)束狀態(tài)和子狀態(tài)是關(guān)鍵中的關(guān)鍵。典型的方法是分類討論。前期不要怕分太多，太細(xì)可以合并。
最后
如果你覺(jué)得這篇文章對(duì)你有一點(diǎn)幫助，請(qǐng)給它一個(gè)大拇指。或者你也可以加入我的開發(fā)交流群：互相學(xué)習(xí)，我們會(huì)有專業(yè)的技術(shù)答疑
如果你覺(jué)得這篇文章對(duì)你有用，請(qǐng)給我們的開源項(xiàng)目一個(gè)小星星：非常感謝！
PHP學(xué)習(xí)手冊(cè)：
技術(shù)交流論壇：
