存档

文章标签 ‘线段树’

线段树

2012年7月16日 1 条评论

---

概述

线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段”或“区间”。树的根节点表示是“整体”的区间,左右子树分别表示这个区间的左半边和右半边。

基本结构及性质

假设要构造一个表示N个区间大小的线段树,线段树的根节点表示区间[0,N-1],然后将区间分成两半,分别为左右子树表示,这样的线段树的节点只有2N-1个,是O(N)级别的,如图所示表示构造区间[1-5]的线段树。

1)存储:

线段树可以使用链状结构动态构造,这样的优点是节省空间,空间复杂度在2N,但是缺点就是编程复杂度大,执行效率低;

所以线段树一般是使用一维数组以完全二叉树的方式来存储,类似堆,这样的编程复杂度低,执行效率高,但是耗费空间,一般来讲,这样情况下都是申请4N的空间,关于这方面的分析请见参考资料。

2)实现细节:

使用一维数组存储,设父节点的下标为idx,则左儿子下标为(idx<<1)+1,右儿子下标为(idx<<1)+2。

一般来讲,线段树的节点必有的两个域为left和right,代表该节点表示区间[left,right],区间的中间节点为mid=(left+right)>>1,它左儿子表示的区间为[left,mid],右儿子表示的区间为[mid+1,right],有时候右儿子的区间为[mid,right],具体是什么取决于实际问题,主要是看解决的问题是针对于“点”还是针对于“区间”,具体可参见本节后面的应用举例部分。

阅读全文...

逆序对 | 逆序数

2012年7月16日 3 条评论

---

设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)【《算法导论》2-4】

现给出一个数列,求该数列中的逆序对数(逆序数)。本节给出三种方法:方法一是最直接的暴力方法;方法二是基于归并分治的思想;方法三是基于线段树的。

解法一

暴力方法最直接,也最容易想到,两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:

	int sum = 0;
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			if(arr[i] > arr[j])
			{
				++sum;
			}
		}
	}
	return sum;

解法二

这种方法最初见于《算法导论》,这里先附上《算法导论》2-4关于逆序对的几点讨论:

阅读全文...

线段覆盖长度

2012年7月16日 4 条评论

---

给定一些线段,线段有起点和终点,求这些线段的覆盖长度,重复的部分只计算一次。

这是在小桥流水博客中看到的一道面试题(小米科技),后来为了练习线段树这个数据结构,就做了一下这道题,本节给出两种方法,一种是基于排序来做的,一种是使用线段树来做的。

方法一:

首先说排序对于处理很多问题都是非常有效的,例如寻找兄弟单词等问题中,经过排序处理后,问题就明朗了很多;

线段覆盖长度也是这样,将线段排序后,然后扫描一遍就可以得到覆盖的长度。具体做法:排序时,先按线段的起始端点排序,如果始点相同则按照末端点排,然后从头扫描,寻找连续段;所谓连续段即下一条线段的始点不大于当前线段的末点就一直扫描,直到找到断层的,计算当前长度,然后继续重复扫描直到最后,便得总长度。代码如下:

阅读全文...