文档章节

线段树和区间树

李韬_varyshare
 李韬_varyshare
发布于 2017/05/20 19:23
字数 1622
阅读 271
收藏 0

区间树 

问题描述1:

假如有四个线段 { 1, 2 }, { 2, 4 }, { 1, 3 }, { 4, 9 } ,问线段(3, 4)与这些线段中有几个是重叠的?

   分析:按照正常思路是先遍历,依次比对左端点3是否在某个线段中,右端点是否在某个线段中, 如果只有四个线段的话这个是推荐的。但是一旦数据量大了复杂度就高,这时我们需要利用二分查找的思想来判断。

  我们先构造一个树,使得只需要判断根节点就知道需不需要搜寻子节点了。比如某个子树最右边是2,那么3,4肯定不会与这些子树下面的线段冲突,这就大大减少了需要查找的数据量。

算法思路:

  1. 构造二叉排序树,以线段左端点作为排序条件。每添加一个节点更新各子树可到的最右端距离
  2. 计算重合:如果目标线段左端点大于当前节点子树可到的最大右端点则返回0.如果目标线段与当前节点线段重合则重合数+1,交给左右节点去计算重合的数量。最终的重合数量是左右节点重合数量之和加当前节点是否与目标节点重合

具体代码

public class LineSegmentTree {
	public int begin;
	public int end;
	public int max_right;
	LineSegmentTree left;
	LineSegmentTree right;

	public LineSegmentTree(int begin, int end) {
		this.begin = begin;
		this.end = end;
//一开始只有一个节点,因此自己作为根节点子树可到的最右端是自己的右端点
		max_right = end;

	}

	private void add(LineSegmentTree child) {
		if (child.begin < begin) {
			if (left == null)
				left = child;
			else
				left.add(child);
		} else {
			if (right == null)
				right = child;
			else
				right.add(child);
		}
//更新当前节点为根节点的子树可到的最右端距离
		if (left != null && left.max_right > max_right)
			max_right = left.max_right;
		if (right != null && right.max_right > max_right)
			max_right = right.max_right;
	}

	public int getCollisionNum(int tbegin, int tend) {
//如果目标节点起始点比当前子树可到最右端还要大,就不会重合返回0
		if (tbegin >= max_right)
			return 0;
		int collisionsnum = 0;
//判断是否与当前节点重合
		if (tend > this.begin&&tbegin<this.end)
			collisionsnum++;
//计算左子树与目标节点重合的线段数量
		if (left != null)
			collisionsnum += this.left.getCollisionNum(tbegin, tend);
		if (right != null)
			collisionsnum += this.right.getCollisionNum(tbegin, tend);
		return collisionsnum;
	}

	public static void main(String[] args) {
		int[][] array = { { 1, 2 }, { 2, 4 }, { 1, 3 }, { 4, 9 } };
		LineSegmentTree head = new LineSegmentTree(array[0][0], array[0][1]);
		for (int i = 1; i < array.length; i++)
			head.add(new LineSegmentTree(array[i][0], array[i][1]));
		System.out.println(head.getCollisionNum(3, 4));

	}
}

线段树

问题描述

假设有以下线段{ 1, 2 }, { 1, 3 }, { 5, 9 } ,求他们合并在一起的线段长度为多长。

 这类题目用区间树就不太好做,虽然也可以做不过效率不高。区间树是一个一个的去找判断是否线段有重合。而线段树则是定义一个大的区间然后将这个区间进行等分,比如长度为100,然后分成一格长度为1的100份。然后只需要判断有多少格被覆盖了就可以算出合并后的总长度。


public class LineSegmentTree {
	public int begin;
	public int end;
	LineSegmentTree left;
	LineSegmentTree right;
	boolean covered;

	public LineSegmentTree() {
	}

	public LineSegmentTree(int begin, int end) {
		this.begin = begin;
		this.end = end;
	}

	private void add(LineSegmentTree child) {
		// 如果已经覆盖了则没必要再计算child是否覆盖当前节点
		if (covered)
			return;
		// 如果不相交则与子树也不会相交
		if (child.begin >= end || child.end <= begin)
			return;
		// 根节点覆盖后下面子树就不用计算是否覆盖,不然会重复
		if (child.begin <= begin && child.end >= end) {
			this.covered = true;
			return;
		}

		if (left != null)
			left.add(child);
		if (right != null)
			right.add(child);
	}

	public void split(int tbegin, int tend) {
		int distance = tend - tbegin;
		this.begin = tbegin;
		this.end = tend;
		if (distance < 2)
			return;
		else {
			this.left = new LineSegmentTree();
			this.right = new LineSegmentTree();
			this.left.split(tbegin, tbegin + distance / 2);
			this.right.split(tbegin + distance / 2, tend);
		}
	}

	public int getCoveredLen() {
		if (this.covered)
			return (end - begin);
		else {
			int coverLen = 0;
			if (this.left != null)
				coverLen += this.left.getCoveredLen();
			if (this.right != null)
				coverLen += this.right.getCoveredLen();
			return coverLen;
		}
	}

	public static void main(String[] args) {
		int[][] array = { { 1, 2 }, { 1, 3 }, { 5, 9 } };
		LineSegmentTree root = new LineSegmentTree();
		root.split(0, 100);//事先分好100份
		for (int i = 0; i < array.length; i++)
			root.add(new LineSegmentTree(array[i][0], array[i][1]));
		System.out.println(root.getCoveredLen());//统计这100份中覆盖的数量
	}
}

实例

拓展

线段树用的地方挺多比如:

一个平面有很多矩形,他们可以重叠,求这些矩形合并后的面积。

一个墙壁贴满海报,海报可以重叠问墙壁被覆盖的面积。

地面刷油漆,按照矩形方式刷了很多不同矩形,矩形可以重叠问地面刷油漆的区域。

等等。

这些思路都是将大区域分割成面积为1的小区域,然后判断有多少区域被覆盖了。

下面写下具体代码:

 

 


import java.awt.Point;

public class AreaUnion {
	AreaUnion leftTop;
	AreaUnion rightTop;
	AreaUnion leftBottom;
	AreaUnion rightBottom;
	Point left;// 左上点坐标
	Point right;// 右下点坐标
	boolean covered;

	public AreaUnion() {
	}

	public AreaUnion(int x1, int y1, int x2, int y2) {
		this(new Point(x1, y1), new Point(x2, y2));
	}

	public AreaUnion(Point left, Point right) {
		this.left = left;
		this.right = right;
	}

	public void split(Point varLeft, Point varRight) {
		this.leftTop = new AreaUnion(varLeft, varRight);
		this.left = varLeft;
		this.right = varRight;
		int yDistance = varLeft.y - varRight.y;
		int xDistance = varRight.x - varLeft.x;
		if (xDistance < 2 && yDistance < 2)
			return;
		// 横坐标方向宽大于2则可以y方向为对称轴对半分
		if (xDistance >= 2) {
			Point tempRight = new Point(varLeft.x + xDistance / 2, varRight.y);
			this.leftTop = new AreaUnion(varLeft, tempRight);

			Point tempLeft = new Point(varLeft.x + xDistance / 2, varLeft.y);
			this.rightTop = new AreaUnion(tempLeft, varRight);
		}

		// 纵坐标方向大于2以x方向为对称轴对半分
		if (yDistance >= 2) {
			AreaUnion tempTopLeft;
			if (leftTop != null) {
				tempTopLeft = leftTop;
				Point tempLeft = new Point(tempTopLeft.left.x,
						tempTopLeft.left.y - yDistance / 2);
				this.leftBottom = new AreaUnion(tempLeft, tempTopLeft.right);

				Point tempRight = new Point(tempTopLeft.right.x,
						tempTopLeft.left.y - yDistance / 2);
				this.leftTop = new AreaUnion(tempTopLeft.left, tempRight);
			}

			if (rightTop != null) {
				tempTopLeft = rightTop;
				Point tempLeft = new Point(tempTopLeft.left.x,
						tempTopLeft.left.y - yDistance / 2);
				this.rightBottom = new AreaUnion(tempLeft, tempTopLeft.right);

				Point tempRight = new Point(tempTopLeft.right.x,
						tempTopLeft.left.y - yDistance / 2);
				this.rightTop = new AreaUnion(tempTopLeft.left, tempRight);
			}
		}
		AreaUnion[] childArea = { this.leftTop, this.leftBottom, this.rightTop,
				this.rightBottom };
		for (AreaUnion i : childArea)
			if (i != null)
				i.split(i.left, i.right);
	}

	public void add(Point varLeft, Point varRight) {
		if (covered)// 已经覆盖过了不用重复计算
			return;
		// 不相交
		if (varRight.x <= this.left.x || varRight.y >= this.left.y)
			return;
		if (varLeft.y <= this.right.y || varLeft.x >= this.right.x)
			return;

		// 完全覆盖
		if (varLeft.x <= left.x && varLeft.y >= left.y && varRight.y <= right.y
				&& varRight.x >= right.x) {
			covered = true;
			return;
		}

		// 覆盖了子树
		AreaUnion[] childArea = { this.leftTop, this.leftBottom, this.rightTop,
				this.rightBottom };
		for (AreaUnion i : childArea)
			if (i != null)
				i.add(varLeft, varRight);
	}

	public int getUnionArea() {
		if (covered) {
			int yDistance = left.y - right.y;
			int xDistance = right.x - left.x;
			return yDistance * xDistance;
		}
		// 找子树覆盖的面积
		int coverArea = 0;
		AreaUnion[] childArea = { this.leftTop, this.leftBottom, this.rightTop,
				this.rightBottom };
		for (AreaUnion i : childArea)
			if (i != null)
				coverArea += i.getUnionArea();
		return coverArea;
	}

	public static void main(String[] args) {
		AreaUnion areaUnion = new AreaUnion();
		areaUnion.split(new Point(0, 4), new Point(4, 0));
		AreaUnion[] areaArr = { new AreaUnion(0, 2, 3, 0),new AreaUnion(0, 4, 2, 0)};
		for(AreaUnion i :areaArr)
			areaUnion.add(i.left, i.right);
		System.out.println(areaUnion.getUnionArea());
	}
}

 

© 著作权归作者所有

李韬_varyshare

李韬_varyshare

粉丝 7
博文 27
码字总数 18588
作品 1
广州
个人站长
私信 提问
加载中

评论(0)

线段树&&线段树的创建线段树的查询&&单节点更新&&区间更新

目录 线段树 什么是线段树? 线段树的创建 线段树的查询 单节点更新 区间更新 未完待续 线段树 实现问题:常用于求数组区间最小值 时间复杂度:(1).建树复杂度:nlogn。(2).线段树算法复杂度...

Chicago_01
2018/08/28
0
0
算法模板——线段树

前言 线段树作为高级数据结构,可以做非常非常多的事情,那么线段树到底是什么呢,我们就此了解下 一.基本概念 线段树并非什么特别高级的东西,顾名思义,它也就是一棵树。那么为什么叫线段树...

qq_39399999
2017/12/07
0
0
解决区间第K大的问题的各种方法

例题:http://poj.org/problem?id=2104 最近可能是念念不忘,必有回响吧,总是看到区间第k大的问题,第一次看到是在知乎上有人面试被弄懵了后来又多次在比赛中看到。以前大概是知道怎么解决但...

GoldenFingers
2018/08/17
0
0
线段树

线段树 主要是涉及到线段树的思路。构造和一些简单的应用。 线段树的应用比较集中,主要是用来处理数组结构里的一些快速查找和修改。以查找数组某区间的最大值这个需求为例子,构建线段树的复...

跑得比谁都慢
2017/12/20
0
0
有趣的 zkw 线段树(超全详解)

zkw segment-tree 真是太棒了(重口味)!写篇博客纪念入门 emmm...首先我们来介绍一下 zkw 线段树这个东西(俗称 "重口味" ,与 KMP 类似,咳咳...) zkw 线段树的介绍 其实 zkw 线段树和普...

Judge_Cheung
2018/08/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

QT

1、https://download.qt.io/archive/qt/ 2、信号与槽

微小宝
29分钟前
27
0
类型隐式转换导致的?No,并不是

疑似类型隐式转换一例 有群友提了下面这样的问题 请教个隐式转换的问题:SELECT count(*) FROM test WHERE time >= 2019-05-17;time列是datetime类型,这条SQL的执行结果是相当于 where 1, 这...

叶金荣
37分钟前
24
0
CentOS7通过Docker安装zabbix

1. 首先,启动空的 MySQL 服务器实例。 # docker run --name mysql-server -t \ -e MYSQL_DATABASE="zabbix" \ -e MYSQL_USER="zabbix" \ -e MYSQL_PASSWORD="zabbix_pwd" \ -e MYSQ......

joininjoy
37分钟前
27
0
如何在JavaScript中合并两个数组并删除重复项 - How to merge two arrays in JavaScript and de-duplicate items

问题: I have two JavaScript arrays: 我有两个JavaScript数组: var array1 = ["Vijendra","Singh"];var array2 = ["Singh", "Shakya"]; I want the output to be: 我希望输出为: var ......

技术盛宴
39分钟前
23
0
震惊!这样终止线程,竟然会导致服务宕机?

在开始之前,我们先来看以下代码会有什么问题? public class ThreadStopExample { public static void main(String[] args) throws InterruptedException { Thread t1 = new Th......

Java中文社群_老王
41分钟前
22
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部