首页 > 算法 数据结构 > 线段树

线段树

2012年7月16日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

概述

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

基本结构及性质

假设要构造一个表示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],具体是什么取决于实际问题,主要是看解决的问题是针对于“点”还是针对于“区间”,具体可参见本节后面的应用举例部分。

有些时候空间过大,需要使用离散化压缩空间,离散化是节省空间的一个很巧妙方法,关于它的举例详见参考资料。

3)基本操作:

线段树支持的操作有:构造,插入,查找,更新,删除;这些操作不一定都有,在实现上也不一定都是一个套路,这都取决于实际问题;实际上,通过在线段树节点上记录不同的信息,线段树可以完成很多不同的任务;线段树的高度为logn,这也就使得线段树可以在O(lgn)的时间完成插入、查询、删除等操作。

应用举例

在处理区间最值问题上,除了动态规划,线段树对于解决数列的区间问题也有着很大的优势,适用于和区间统计有关的问题。例如对某些数据可以按区间划分、按区间动态修改、按区间进行频繁查询,那么使用线段树可以达到较快的查询速度。

例如:给一个数的数列[A1,A2,…  An],并且可能多次进行如下操作:

1)   对序列中的某个数进行加减

2)  询问该序列任意一个子区间[i,j]的和是多少

显然,线段树可以在O(lgn)的时间完成这些操作,每个区间对应的节点增加一个记录区间和的信息即可,然后:

1)   操作一:因为序列里面Ai最多只会被线段树的logn个节点覆盖。只要求对线段树覆盖Ai的节点的区间和sum进行加减操作即可。

2)  操作二:只需找到区间所覆盖的区域,然后将区域和累加即可

这里引用《线段树与树状数组》(见参考资料)中的一句话,我觉得作者说的非常好:

用线段树解题,关键是要想清楚每个节点要存哪些信息(当然区间起终点,以及左右子节点指针是必须的),以及这些信息如何高效更新,维护,查询。不要一更新就更新到叶子节点,那样更新效率最坏就可能变成O(n)的了。

先建树,然后插入数据,然后更新,查询。

代码及实现

附上线段树入门的几个问题及代码,前两个问题的代码可以直接点击下载,也可到资源区下载下面所有代码的打包:

线段树求区间最大值(代码)

线段树求点在线段中的出现次数(代码)

线段树求线段覆盖长度(博文)

线段树求逆序数(博文)

本文相关代码可以到这里下载。

(全文完)

参考资料:

杨弋讲稿《线段树》

线段树空间占用分析:http://comzyh.tk/blog/archives/479/

线段树离散化举例(该文2.2节):http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html

线段树百度百科:http://baike.baidu.com/view/670683.htm

线段树入门举例:http://hi.baidu.com/alpc62/blog/item/469edeca0043e382c8176875.html

线段树和树状数组(北大郭炜):http://poj.org/summerschool/1_interval_tree.pdf

线段树|董的博客:http://dongxicheng.org/structure/segment-tree/

  • http://zwl.me zwl

    精彩的分享,很不错。。。