比如我们有一个大小为6的数组，其索引为0，1，2，3，4，5，那么我们就可以构建出如下的一颗线段树，下图所示：
在这里插入图片描述考虑到一棵完全二叉树，假设右k层，则其总数为2^0+2^1+….+2^k=2^(k+1)-1,所以针对一棵线段树，其最好情况下是一棵满二叉树，这时候线段是的大小为2*n即可，但是往往由于数据因素可能会变成一课完全二叉树，而不是恰好就是满二叉树，这时候如果需要涵盖所有的数据，就需要开辟2*（2*n)才行
所以根据上面的阐述，假设我们有一个数组data[n],那么开辟的tree数组大小就是4n。构造函数如下：
privateE[]tree;privateE[]data;privateMergerEmerger;publicSegmentTree(E[]value,MergerEmerger){this.data=(E[])newObject[value.length];for(inti=0;ivalue.length;i++){data[i]=value[i];}this.tree=(E[])newObject[4*value.length];this.merger=merger;buildSegmentTree(0,0,this.data.length-1);}
首先我们可以通过递归方式插入数据：针对每一个区间，都为分裂成两个区块，直到不可分裂为止（递归终止条件是单独的index成为区块）
/****
paramindex:该段的索引*paramleft：线段树的左段，对应data里面的索引*paramright：线段树的右段，对应data里面的索引*return:该段存储的值*/publicEbuildSegmentTree(intindex,intleft,intright){if(left==right){tree[index]=data[left];returntree[index];}intmid=left+(right-left)/2;//分裂成2个段//左段EleftValue=buildSegmentTree(2*index+1,left,mid);//右段ErightValue=buildSegmentTree(2*index+2,mid+1,right);//聚合左段和右段的值tree[index]=this.merger.merge(leftValue,rightValue);returntree[index];}```根据区间查询结果值：本质上还是查query的范围对应线段树的哪些区间组合。publicEqueryByRange(intindex,inttreeL,inttreeR,intleft,intright){
if(left==treeLright==treeR){returntree[index];}intmid=treeL+(treeR-treeL)/2;if(right=mid){returnqueryByRange(2*index+1,treeL,mid,left,right);}if(left=mid+1){returnqueryByRange(2*index+2,mid+1,treeR,left,right);}//即在左边又在右边returnmerger.merge(queryByRange(2*index+1,treeL,mid,left,mid),queryByRange(2*index+2,mid+1,treeR,mid+1,right));}
更新原始数组索引的值:
publicvoidupdate(intindex,Ee){
updateDg(0,0,data.length-1,index,e);}privatevoidupdateDg(inttreeIndex,intl,intr,intdataIndex,Ee){if(l==r){tree[treeIndex]=e;return;}intmid=l+(r-l)/2;if(dataIndexmid){updateDg(2*treeIndex+2,mid+1,r,dataIndex,e);}else{updateDg(2*treeIndex+1,l,mid,dataIndex,e);}tree[treeIndex]=merger.merge(tree[2*treeIndex+1],tree[2*treeIndex+2]);}
线段树比较适合针对一批数组，需要频繁得出查询范围区间的值得情况。其与数组之间的对比如下：![在这里插入图片描述](