php開發(fā)手冊線段樹是為區(qū)間更新和區(qū)間查詢而生的數(shù)據(jù)結(jié)構(gòu)，旨在快速解決區(qū)間問題力軟開發(fā)框架的開發(fā)手冊
2022-03-25
線段樹是一種用于區(qū)間更新和區(qū)間查詢的數(shù)據(jù)結(jié)構(gòu)，旨在快速解決區(qū)間問題。
一般來說，線段樹不會添加節(jié)點，也不支持動態(tài)添加節(jié)點。段樹也是二叉樹的一種，但它的節(jié)點是由一個區(qū)間定義的。葉節(jié)點是具有單個間隔的節(jié)點。所以線段樹本質(zhì)上是一棵區(qū)間樹。
我們在搜索的時候，只需要找出哪些子區(qū)間構(gòu)成了結(jié)果區(qū)間。
實現(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 用于唯一地表征這個區(qū)間。那么其他的內(nèi)容就和標準的二叉樹沒什么區(qū)別了。
???
建樹過程
和二叉樹構(gòu)造沒什么區(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é)點的判斷條件是 left == 。在其他方面，它與二叉樹沒有什么不同。
???
查詢區(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è)置當前節(jié)點的區(qū)間為[L,R]，那么對于區(qū)間[l,r]的最大值，需要進行分類討論。如果LR區(qū)間的中點Mid在lr區(qū)間的左側(cè)，則max(lr) = max( , l, r); 如果LR區(qū)間的中點在lr區(qū)間的右側(cè)，則max(lr) = max(left , l, r); 如果 Mid 在 lr 區(qū)間內(nèi)，max(lr) = max(left , l, mid) 和 max( , mid+1, r) 中的較大者。
???
我們來看看測試用例和運行結(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)在需要改變原來的建樹過程。首先php開發(fā)手冊，將 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的維護
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ù)制代碼測試過程和結(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
單點更新
/**
* 這里的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ù)制代碼更新時采用遞歸的方式從左右節(jié)點不斷尋找需要更新的區(qū)間，同時更新上級節(jié)點的最新值。
總結(jié)
您可以根據(jù)需要擴展它。請記住小程序開發(fā)，線段樹是以區(qū)間為維度的二叉樹，或以二維維度為特征的二叉樹。普通的二叉樹只有一維。這樣php開發(fā)手冊，我們在計算多維值的時候網(wǎng)站優(yōu)化，其實可以這樣構(gòu)造線段樹（二維樹、三維樹、n維樹）。不管樹的維數(shù)多少，找到結(jié)束狀態(tài)和子狀態(tài)是關(guān)鍵中的關(guān)鍵。典型的方法是分類討論。前期不要怕分太多，太細可以合并。
最后
如果你覺得這篇文章對你有一點幫助，請給它一個大拇指?；蛘吣阋部梢约尤胛业拈_發(fā)交流群：互相學(xué)習(xí)，我們會有專業(yè)的技術(shù)答疑
如果你覺得這篇文章對你有用，請給我們的開源項目一個小星星：非常感謝！
PHP學(xué)習(xí)手冊：
技術(shù)交流論壇：
