Java数据结构之线段树的原理与实现

目录简介实现思路节点定义构建线段树求解区间和更新线段树

简介

线段树是一种二叉搜索树，是用来维护区间信息的数据结构。可以在O(logN)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。接下来我以实现区间求和为例子来讲解线段树（最大值和最小值与求和实现方式几乎无异），假设存在一个数组[1,4,6,3,9]。

实现思路

从线段树的定义，我们首先需要定义一个树节点，节点包含区间和（23），区间（[1-5]），左节点，右节点等。（如果要实现求区间最大值，最小值，则还需包含这些）。然后需要提供构建线段树，线段树支持修改节点操作方法。

节点定义

@Data

publicstaticclassNode{

//区间起始下标

privateintstart;

//区间结尾下标

privateintend;

//当前区间和值

privateinthttp://value;

privateNodeleft;

privateNoderight;

Node(intstart,intend,intvalue) {

this.start=start;

this.end=end;

this.value=value;

}

}

构建线段树

因为构建线段树时候需要计算当前区间和，所以我们可以先初始化一个前缀和数组，在构建线段树时候利用下标快速计算出区间和,同时为了保证每个节点有一致的操作，初始化一个头节点，指向root（这是链表树等常用的简化操作的方法）

//head 指向线段树root节点的指针，使得root节点与其余节点操作保持一致

Nodehead;

intsize;

Listnums;

//前缀和数组，便于构建线段树时候计算区间值，用于初次构建辅助

ListprefixSum;

publicvoidinit(Listnums) {

//初始化一个头节点，便于操作

this.head=newNode(-1,-1,-1);

this.nums=nums;

//初始化前缀和数组

prefixSum=newArrayList<>(nums.size());

prefixSum.add(0);

for(inti=0;i

prefixSum.add(prefixSum.get(prefixSum.size()-1)+nums.get(i));

}

//构建线段树

this.build(1,nums.size());

size=nums.size();

}

//构建线段树

publicvoidbuild(intstart,intend) {

Noderoot=newNode(start,end,prefixSum.get(end)-prefixSum.get(start-1));

//将头节点右子树指向root

head.right=root;

//从root开始构建线段树

this.madeChild(root,start,end);

}

privatevoidmadeChild(Nodenode,intstart,intend) {

if(start>=end) {

return;

}

//分个左右子树，左子树取start～mid，右子树取mid+1～end

intmid=start+((end-start)>>1);

if(start<=mid) {

Nodeleft=newNode(start,mid,prefixSum.get(mid)-prefixSum.get(start-1));

node.left=left;

madeChild(left,start,mid);

}

if(mid+1<=end) {

Noderight=newNode(mid+1,end,prefixSum.get(end)-prefixSum.get(mid));

node.right=right;

madeChild(right,mid+1,end);

}

}

求解区间和

求解区间和过程就是遍历线段树，将求解区间与当前节点区间进行比较，如果全部存在于左子树或者右子树，则直接深度继续在左子树右子树遍历即可，但是如果求解区间在当前节点的左右子树均有部分，则需要将当前区间分为两个部分，然后分别深度遍历左右子树，最后将结果相加。

//求解区间和

publicintfindSectionSum(intstart,intend) {

//深度遍历线段树，找到对应区间

if(start<1||end>size||start>end) {

return-1;

}

returndfsFindSectionSum(head.right,start,end);

}

/**

* 深度遍历线段树结构，分为三种情况

* 1.区间在当前节点的左子树中

* 2.区间在当前节点的右子树中

* 3.左子树中一部分，右子树中一部分

* @param node

* @param start

* @param end

* @return

*/

privateintdfsFindSectionSum(Nodenode,intstart,intend) {

if(node.start==start&&node.end==end) {

//找到区间

returnnode.value;

}

if(this.isContain(node.left.start,node.left.end,start,end)) {

//在左子树中

returnthis.dfsFindSectionSum(node.left,start,end);

}

if(this.isContain(node.right.start,node.right.end,start,end)) {

http:// //包含在右子树中

returnthis.dfsFindSectionSum(node.right,start,end);

}

//左边一部分，右边一部分

returnthis.dfsFindSectionSum(node.left,start,node.left.end)+this.dfsFindSectionSum(node.right,node.right.start,end);

}

/**

* 判断区间[start2, end2]是否包含在[start1, end1]中

* @param start1

* @param end1

* @param start2

* @param end2

* @return

*/

privatebooleanisContain(intstart1,intend1,intstart2,intend2){

returnstart2>=start1&&end2<=end1;

}

更新线段树

当更新指定位置元素的值的时候，我们需要将线段树中区间包含该节点的区间和进行更新。我们可以从根节点开始深度遍历线段树，如果当前节点包含该位置，我们更新区间和，然后根据当前节点左右子节点的区间，判断走左子树还是右ykSpI子树，直至更新到叶子节点，则更新完成。

//更新线段树，将index位置的值更新为value，需要更新沿路的值

publicvoidupdate(intindex,intvalue) {

Noderoot=head.right;

while(null!=root) {

if(index>=root.start&&index<=root.end) {

root.value+=value-nums.get(index-1);

}

intmid=root.start+((root.end-root.start)>>1);

if(index<=mid) {

root=root.left;

continue;

}

root=root.right;

}

nums.set(index-1,value);

}

以上就是java数据结构之线段树的原理与实现的详细内容，更多关于Java 线段树的资料请关注我们其它相关文章！

prefixSum.add(prefixSum.get(prefixSum.size()-1)+nums.get(i));

}

//构建线段树

this.build(1,nums.size());

size=nums.size();

}

//构建线段树

publicvoidbuild(intstart,intend) {

Noderoot=newNode(start,end,prefixSum.get(end)-prefixSum.get(start-1));

//将头节点右子树指向root

head.right=root;

//从root开始构建线段树

this.madeChild(root,start,end);

}

privatevoidmadeChild(Nodenode,intstart,intend) {

if(start>=end) {

return;

}

//分个左右子树，左子树取start～mid，右子树取mid+1～end

intmid=start+((end-start)>>1);

if(start<=mid) {

Nodeleft=newNode(start,mid,prefixSum.get(mid)-prefixSum.get(start-1));

node.left=left;

madeChild(left,start,mid);

}

if(mid+1<=end) {

Noderight=newNode(mid+1,end,prefixSum.get(end)-prefixSum.get(mid));

node.right=right;

madeChild(right,mid+1,end);

}

}

求解区间和

求解区间和过程就是遍历线段树，将求解区间与当前节点区间进行比较，如果全部存在于左子树或者右子树，则直接深度继续在左子树右子树遍历即可，但是如果求解区间在当前节点的左右子树均有部分，则需要将当前区间分为两个部分，然后分别深度遍历左右子树，最后将结果相加。

//求解区间和

publicintfindSectionSum(intstart,intend) {

//深度遍历线段树，找到对应区间

if(start<1||end>size||start>end) {

return-1;

}

returndfsFindSectionSum(head.right,start,end);

}

/**

* 深度遍历线段树结构，分为三种情况

* 1.区间在当前节点的左子树中

* 2.区间在当前节点的右子树中

* 3.左子树中一部分，右子树中一部分

* @param node

* @param start

* @param end

* @return

*/

privateintdfsFindSectionSum(Nodenode,intstart,intend) {

if(node.start==start&&node.end==end) {

//找到区间

returnnode.value;

}

if(this.isContain(node.left.start,node.left.end,start,end)) {

//在左子树中

returnthis.dfsFindSectionSum(node.left,start,end);

}

if(this.isContain(node.right.start,node.right.end,start,end)) {

http:// //包含在右子树中

returnthis.dfsFindSectionSum(node.right,start,end);

}

//左边一部分，右边一部分

returnthis.dfsFindSectionSum(node.left,start,node.left.end)+this.dfsFindSectionSum(node.right,node.right.start,end);

}

/**

* 判断区间[start2, end2]是否包含在[start1, end1]中

* @param start1

* @param end1

* @param start2

* @param end2

* @return

*/

privatebooleanisContain(intstart1,intend1,intstart2,intend2){

returnstart2>=start1&&end2<=end1;

}

更新线段树

当更新指定位置元素的值的时候，我们需要将线段树中区间包含该节点的区间和进行更新。我们可以从根节点开始深度遍历线段树，如果当前节点包含该位置，我们更新区间和，然后根据当前节点左右子节点的区间，判断走左子树还是右ykSpI子树，直至更新到叶子节点，则更新完成。

//更新线段树，将index位置的值更新为value，需要更新沿路的值

publicvoidupdate(intindex,intvalue) {

Noderoot=head.right;

while(null!=root) {

if(index>=root.start&&index<=root.end) {

root.value+=value-nums.get(index-1);

}

intmid=root.start+((root.end-root.start)>>1);

if(index<=mid) {

root=root.left;

continue;

}

root=root.right;

}

nums.set(index-1,value);

}

以上就是java数据结构之线段树的原理与实现的详细内容，更多关于Java 线段树的资料请关注我们其它相关文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。