关于javascript:用Java实现线段树

线段树是为区间更新和区间查问而生的数据结构，旨在疾速解决区间问题。

一般来说，线段树是不会加节点的，也不反对动静增加节点。线段树也是二叉树的一种，不过它的节点是以一个区间来定义节点的。具备一个繁多区间的就是叶子节点。所以线段树，实质上就是一棵区间树。

咱们在查找的时候，只须要找出后果区间由哪些子区间形成即可。

实现代码
首先定义出根底的构造

public class SegmentTree {


private Integer value;
private Integer maxValue;

private Integer l;
private Integer r;

private SegmentTree leftChild;
private SegmentTree rightChild;

}
复制代码
l和r用来惟一刻画这个区间。而后其余的内容，与规范的二叉树没得任何区别。

建树过程
与二叉树建树没得区别，咱们这里采纳前序建树的形式进行。代码如下：

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;

}
复制代码
能够看见，这里的叶子节点判断条件就是 left == right。其余方面和二叉树没有任何区别。

查问区间最大值
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("获取了区间 [" + 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);
    }
}

}
复制代码
从下面的代码剖析，设以后节点的区间为【L,R】，那么对于区间[l,r]的最大值来说，就须要进行分类探讨，如果LR的区间中点Mid在lr区间的右边，那么max(lr) = max(右子树,l,r)；如果LR的区间中点在lr区间的左边，则max(lr) = max(左子树,l,r)；如果Mid在lr区间外面，则 max(lr) = max(左子树,l,mid) 和 max(右子树,mid+1,r)中的较大值。

上面咱们来看看测试用例和运行后果：

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));

}
复制代码
后果如下

获取了区间 [0,9] 的最大值7 获取了区间 [10,14] 的最大值9 获取了区间 [15,16] 的最大值8 9

获取区间和
当初须要对原来的建树过程进行革新，首先，在根底构造中增加sum字段

public class SegmentTree {

private Integer value;
private Integer maxValue;
private Integer sum;

private Integer l;
private Integer r;

private SegmentTree leftChild;
private SegmentTree rightChild;

}
复制代码
而后在建树办法中，增加对和的保护

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;

}
复制代码
而后获取总和

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("获取了区间 [" + 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;
    }
}

}
复制代码
测试程序和后果如下：

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));

}
复制代码
获取了区间 [0,2] 的和11 获取了区间 [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());

}
复制代码
更新的时候也是利用递归的办法，一直从左右节点中寻找到须要被更新的区间，同时更新下级节点的最新值。

总结
能够按需进行延长，记住一点，线段树是以区间为维度的二叉树，或者说，是以二维维度进行刻画的二叉树，一般二叉树只有一维。这样一来，咱们在计算多维度的值的时候，其实也能够利用这样的形式构建线段树（二维树，三维树，n维树）。不论几维树，找到完结状态和上级子状态就是要害中的要害。典型的办法就是分类探讨，后期不必怕分得过细，细了能够进行合并。

最初
如果你感觉此文对你有一丁点帮忙，点个赞。或者能够退出我的开发交换群：1025263163互相学习，咱们会有业余的技术答疑解惑

如果你感觉这篇文章对你有点用的话，麻烦请给咱们的开源我的项目点点star:http://github.crmeb.net/u/defu不胜感激！

PHP学习手册：https://doc.crmeb.com
技术交换论坛：https://q.crmeb.com

关于javascript:用Java实现线段树

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于javascript:用Java实现线段树

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复