用Java实现线段树

　　线段树是为区间更新和区间查询而生的数据结构，旨在快速解决区间问题。
　　一般来说，线段树是不会加节点的，也不支持动态添加节点。线段树也是二叉树的一种，不过它的节点是以一个区间来定义节点的。具有一个单一区间的就是叶子节点。所以线段树，本质上就是一棵区间树。
　　我们在查找的时候，只需要找出结果区间由哪些子区间构成即可。实现代码
　　首先定义出基础的结构publicclassSegmentTree｛privateIntegervalue；privateIntegermaxValue；privateIntegerl；privateIntegerr；privateSegmentTreeleftChild；privateSegmentTreerightChild；｝复制代码
　　l和r用来唯一刻画这个区间。然后其他的内容，与标准的二叉树没得任何区别。
　　建树过程
　　与二叉树建树没得区别，我们这里采用前序建树的方式进行。代码如下：publicstaticSegmentTreebuildTree（intleft，intright，int〔〕value）｛if（leftright）｛returnnull；｝SegmentTreenodenewSegmentTree（）；node。setValue（value〔left〕）；node。setL（left）；node。setR（right）；if（leftright）｛TODO：2022117退出条件node。setMaxValue（node。getValue（））；returnnode；｝intmid（leftright）1；node。setLeftChild（buildTree（left，mid，value））；node。setRightChild（buildTree（mid1，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（）））；｝｝returnnode；｝复制代码
　　可以看见，这里的叶子节点判断条件就是leftright。其他方面和二叉树没有任何区别。
　　查询区间最大值publicstaticIntegergetMaxValue（SegmentTreesegmentTree，intleft，intright）｛if（Objects。isNull（segmentTree））returnnull；if（segmentTree。getL（）leftsegmentTree。getR（）right）｛System。out。println（获取了区间〔left，right〕的最大值segmentTree。getMaxValue（））；returnsegmentTree。getMaxValue（）；｝intsegMid（segmentTree。getL（）segmentTree。getR（））1；if（segMidleft）｛returngetMaxValue（segmentTree。getRightChild（），left，right）；｝if（segMidright）｛returngetMaxValue（segmentTree。getLeftChild（），left，right）；｝TODO：2022117左半边答案IntegerleftMaxgetMaxValue（segmentTree。getLeftChild（），left，segMid）；IntegerrightMaxgetMaxValue（segmentTree。getRightChild（），segMid1，right）；if（Objects。isNull（leftMax））｛if（Objects。isNull（rightMax））｛return100000；｝else｛returnrightMax；｝｝else｛if（Objects。isNull（rightMax））｛returnleftMax；｝else｛returnMath。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（右子树，mid1，r）中的较大值。
　　下面我们来看看测试用例和运行结果：publicstaticvoidmain（String〔〕args）｛int〔〕anewint〔〕｛2，5，4，7，6，0，1，1，2，3，6，7，0，2，9，8，5，4，7，2｝；SegmentTreesegmentTreebuildTree（0，a。length1，a）；System。out。println（getMaxValue（segmentTree，0，16））；｝复制代码
　　结果如下
　　获取了区间〔0，9〕的最大值7获取了区间〔10，14〕的最大值9获取了区间〔15，16〕的最大值89获取区间和
　　现在需要对原来的建树过程进行改造，首先，在基础结构中添加sum字段publicclassSegmentTree｛privateIntegervalue；privateIntegermaxValue；privateIntegersum；privateIntegerl；privateIntegerr；privateSegmentTreeleftChild；privateSegmentTreerightChild；｝复制代码
　　然后在建树方法中，添加对和的维护publicstaticSegmentTreebuildTree（intleft，intright，int〔〕value）｛if（leftright）｛returnnull；｝SegmentTreenodenewSegmentTree（）；node。setValue（value〔left〕）；node。setL（left）；node。setR（right）；if（leftright）｛TODO：2022117退出条件node。setMaxValue（node。getValue（））；node。setSum（node。getValue（））；returnnode；｝intmid（leftright）1；node。setLeftChild（buildTree（left，mid，value））；node。setRightChild（buildTree（mid1，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（）leftsegmentTree。getR（）right）｛System。out。println（获取了区间〔left，right〕的和segmentTree。getSum（））；returnsegmentTree。getSum（）；｝intsegMid（segmentTree。getL（）segmentTree。getR（））1；if（segMidleft）｛returngetSum（segmentTree。getRightChild（），left，right）；｝if（segMidright）｛returngetSum（segmentTree。getLeftChild（），left，right）；｝TODO：2022117左半边答案IntegerleftSumgetSum（segmentTree。getLeftChild（），left，segMid）；IntegerrightSumgetSum（segmentTree。getRightChild（），segMid1，right）；if（Objects。isNull（leftSum））｛if（Objects。isNull（rightSum））｛returnsegmentTree。getSum（）；｝else｛returnrightSum；｝｝else｛if（Objects。isNull（rightSum））｛returnleftSum；｝else｛returnleftSumrightSum；｝｝｝复制代码
　　测试程序和结果如下：publicstaticvoidmain（String〔〕args）｛int〔〕anewint〔〕｛2，5，4，7，6，0，1，1，2，3，6，7，0，2，9，8，5，4，7，2｝；SegmentTreesegmentTreebuildTree（0，a。length1，a）；System。out。println（getSum（segmentTree，0，3））；｝复制代码
　　获取了区间〔0，2〕的和11获取了区间〔3，3〕的和718单点更新这里的leftrightparamsegmentTreeparamleftparamrightparamvaluepublicstaticvoidupdate（SegmentTreesegmentTree，intleft，intright，intvalue）｛if（segmentTree。getL（）leftsegmentTree。getR（）right）｛segmentTree。setValue（value）；segmentTree。setMaxValue（value）；segmentTree。setSum（value）；return；｝intmid（segmentTree。getL（）segmentTree。getR（））1；if（midleft）｛update（segmentTree。getLeftChild（），left，right，value）；｝if（midleft）｛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。netudefu不胜感激！
　　PHP学习手册：https：doc。crmeb。com
　　技术交流论坛：https：q。crmeb。com