博客

线段树的创建

代码是以求和为例

private void buildSegmentTree(int treeIndex,int l,int r)；

treeIndex 是当前的位置，就是从头部，

l是左边界，r是右边界

buildSegmentTree(0,0,data.length-1);

mid求中间的位置 吧线段树分为两个部分 左边和右边

左边的开始边界就是l，最后边界就是mid

右边的边界开始是mid+1,末尾就是r

int mid=l+(r-l)/2;// (l+r)/2可以这样写，但是为了防止溢出l+(r-l)/2

左边一直递归，右边一样

buildSegmentTree(leftTreeIndex, l, mid);//左边节点

buildSegmentTree(rightTreeIndex, mid+1, r);//右边节点

最后是相加，因为不能扩展相加，自己定义了融合方法 merger

tree[treeIndex]=merger.merge(data[leftTreeIndex],data[r]);

        //在treeIndex的位置创建表示区间[l...r]的线段树
	private void buildSegmentTree(int treeIndex,int l,int r){
		
		if(l==r){//相等 一个位置就是左边或者最后一个
			tree[treeIndex]=data[l];
			return ;
		}
		
		int leftTreeIndex=leftChild(treeIndex);//左边节点
		int rightTreeIndex=rightChild(treeIndex);//右节点
		
		int mid=l+(r-l)/2;// (l+r)/2可以这样写，但是为了防止溢出l+(r-l)/2
		buildSegmentTree(leftTreeIndex, l, mid);//左边节点
		buildSegmentTree(rightTreeIndex, mid+1, r);//右边节点
		
		
		tree[treeIndex]=merger.merge(data[leftTreeIndex],data[r]);
	}

融合的代码

package com.binglian.SegmentTree;

/**
 * 融合器,两个相加
 * @author binglian
 *
 */
public interface Merger<E> {
	
	E merge(E a,E b);

	
}

主方法这里用到了jdk8的特性

吧匿名函数改为了拉姆达表达式（简化了函数）

package com.binglian.SegmentTree;

public class Main {

	public static void main(String[] args) {

		Integer[] nums={-2,0,3,-5,2,-1};
//		SegmentTree<Integer> segmentTree=new SegmentTree<Integer>(nums,new Merger<Integer>() {
//			
//			public Integer merge(Integer a,Integer b){
//				return a+b;
//			}
//		});
		
		//上面的匿名函数可以表示如下的简便方法
		SegmentTree<Integer> segmentTree=new SegmentTree<Integer>(nums,(a,b)->a+b);
		System.out.println(segmentTree);
	}

}