简单线段树（求区间的并集）

        本文讲述简单的线段树，与我上一篇的区间树解决的问题不同，本题是给定一个大的线段（已知起点与终点），然后再给出众多线段（已知起点与终点），求这众多线段映射到那个大线段上的总长度。解决方案是先将该大线段二分，并将二分后的线段作为节点，创建二叉树。例如，大线段为[2, 10)， 则可以创建如下二叉树：

                                                              [2, 10)

                              [2, 6)                                                        [6, 10)

                [2, 4)                     [4, 6)                            [6, 8)                   [8, 10)

        [2, 3)      [3, 4)       [4, 5)      [5, 6)               [6, 7)    [7, 8)        [8, 9)    [9, 10) 

每个节点需要增加的一个域是是否被覆盖，也就是说当添加一个线段时，如果根节点已经被覆盖，则就可以不判断了。

代码如下：

class SegTree {
	private int begin;
	private int end;
	private boolean isOver;  //是否被覆盖

	private SegTree l;
	private SegTree r;

	public SegTree(int begin, int end) {
		this.begin = begin;
		this.end = end;
	}
	//将线段二分
	public void split() {
		if (end - begin < 2)
			return;
		int mid = (begin + end) / 2;
		l = new SegTree(begin, mid);
		r = new SegTree(mid, end);
		l.split();
		r.split();
	}
	//添加线段
	public void add(int a, int b) {
		if (isOver)
			return;
		if (begin >= b || end <= a)
			return;
		if (begin >= a && end <= b) {
			isOver = true;
			return;
		}
		if (l != null)
			l.add(a, b);
		if (r != null)
			r.add(a, b);
	}
	//获取覆盖长度
	public int getOverLength() {
		if (isOver)
			return end - begin;
		int n = 0;
		if(l != null) {
			n += l.getOverLength();
		}
		if(r != null) {
			n += r.getOverLength();
		}
		return n;
	}
}

public class SegTreeTest {

	public static void main(String[] args) {
		SegTree root = new SegTree(0, 10);
		root.split();

		root.add(1, 2);
		root.add(2, 3);
		root.add(3, 4);
		root.add(5, 9);
		root.add(1, 3);

		int len = root.getOverLength();
		System.out.println(len);
	}

}