线段树是一种区间更新和区间查询的数据结构，旨在快速解决区间问题。一般来说，线段树是不添加节点的，也不支持动态添加节点。线段树也是二叉树的一种，只不过它的节点是用一个区间来定义的。具有单一范围的是叶节点。所以线段树本质上是一棵区间树。我们在查找的时候，只需要找出结果区间由哪些子区间组成即可。实现代码先定义基本结构publicclassSegmentTree{privateIntegervalue;privateIntegermaxValue;privateIntegerl;privateIntegerr;privateSegmentTreeleftChild;privateSegmentTreerightChild;}复制代码l和r来唯一描述这个区间。那么其他的内容就和标准的二叉树没什么区别了。树构建过程和二叉树构建没有区别。我们这里使用预序树的构建方法。代码如下：publicstaticSegmentTreebuildTree(intleft,intright,int[]value){if(left>right){returnnull;}SegmentTreenode=newSegmentTree();node.setValue(value[left]);node.setL(left);node.setR(right);if(left==right){//TODO:2022/1/17退出条款node.setMaxValue(node.getValue());returnnode;}intmid=(left+right)>>>1;node.setLeftChild(buildTree(left,mid,value));node.setRightChild(buildTree(mid+1,right,value));if(对象.isNull(node.getLeftChild())){如果(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()));}}returnnode;}复制代码可以看看，这里的叶子节点的判断条件是left==right，其他方面和二叉树没有区别。查询区域间最大价值publicstaticIntegergetMaxValue(SegmentTreesegmentTree,intleft,intright){if(Objects.isNull(segmentTree))returnnull;if(segmentTree.getL()==left&&segmentTree.getR()==right){System.out.println("获取了区间["+left+","+right+"]的最大价值"+segmentTree.getMaxValue());返回segmentTree.getMaxValue();}intsegMid=(segmentTree.getL()+segmentTree.getR())>>>1;if(segMid=right){returngetMaxValue(segmentTree.getLeftChild(),left,right);}//TODO:2022/1/17左半边答案IntegerleftMax=getMaxValue(segmentTree.getLeftChild(),left,segMid);整数rightMax=getMaxValue(segmentTree.getRightChild(),segMid+1,right);if(Objects.isNull(leftMax)){if(Objects.isNull(rightMax)){return-100000;}else{返回rightMax;}}else{if(Objects.isNull(rightMax)){returnleftMax;}else{returnMath.max(leftMax,rightMax);}}}复制代码从上面的代码分析，设当前节点的区间为[L,R]，则对于区间[l,r]的最大值，需要分类讨论。如果LR区间Mid的中点在lr区间的左侧，则max(lr)=max(rightsubtree,l,r)；如果LR区间的中点在lr区间的右侧，则max(lr)=max(leftsubtree,l,r)；如果Mid在lr区间内，则max(lr)=max(leftsubtree,l,mid)和max(rightsubtree,mid+1,r)取较大值来看看测试用例和运行结果：publicstaticvoidmain(String[]args){int[]a=newint[]{2,5,4,7,6,0,1,-1,2,3,6,7,0,2,9,8,5,4,7,2};SegmentTreesegmentTree=buildTree(0,a.length-1,a);System.out.println(getMaxValue(segmentTree,0,16));}复制代码结果如下获取区间[0,9]的最大值7获取区间[10,14]的最大值9获取区间[15]的最大值,16]89getInterval现在需要修改原来的树构建过程。首先添加求和字段publicclassSegmentTree{privateIntegervalue;privateIntegermaxValue;privateIntegersum;privateIntegerl;privateIntegerr;privateSegmentTreeleftChild;privateSegmentTreerightChild;}复制代码，添加求和的维护在树构建方法publicstaticSegmentTreebuildTree(intleft,intright,int[]value){if(left>right){returnnull;}SegmentTreenode=newSegmentTree();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());返回节点；}intmid=(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());}}returnnode;}复制代码然后获取总和publicstaticIntegergetSum(SegmentTreesegmentTree,intleft,intright){if(Objects.isNull(segmentTree))returnnull;if(segmentTree.getL()==left&&segmentTree.getR()==right){System.out.println("获取区间["+left+","+right+"]"+segmentTree.getSum());返回segmentTree.getSum();}intsegMid=(segmentTree.getL()+segmentTree.getR())>>>1;if(segMid=right){returngetSum(segmentTree.getLeftChild(),left,right);}//TODO:2022/1/17lefthalfanswerIntegerleftSum=getSum(segmentTree.getLeftChild(),left,segMid);整数rightSum=getSum(segmentTree.getRightChild(),segMid+1,right);if(Objects.isNull(leftSum)){if(Objects.isNull(rightSum)){returnsegmentTree.getSum();}else{返回rightSum;}}else{if(Objects.isNull(rightSum)){returnleftSum;}else{返回leftSum+rightSum;}}}复制代码测试程序及结果如下：publicstaticvoidmain(String[]args){int[]a=newint[]{2,5,4,7,6,0,1,-1,2,3,6,7,0,2,9,8,5,4,7,2};SegmentTreesegmentTree=buildTree(0,a.length-1,a);System.out.println(getSum(segmentTree,0,3));}复制代码得到区间[0,2的总和]并得到11区间[3,3]与718单点更新之和/***这里left==right**@paramsegmentTree*@paramleft*@paramright*@paramvalue*/publicstaticvoidupdate(SegmentTreesegmentTree,intleft,intright,intvalue){if(segmentTree.getL()==left&&segmentTree.getR()==right){segmentTree.setValue(value);segmentTree.setMaxValue(值);segmentTree.setSum(值);return;}intmid=(segmentTree.getL()+segmentTree.getR())>>>1;if(mid>=left){update(segmentTree.getLeftChild(),left,right,value);}if(mid
