线段树汇总


其他资料:

百度百科:

http://baike.baidu.com/view/670683.htm

NotOnlySuccess

【完全版线段树】:http://www.notonlysuccess.com/?p=978

【线段树专辑】:http://www.notonlysuccess.com/?p=59

phylps@bmy

线段树总结】:http://duanple.blog.163.com/blog/static/70971767200922110494318/

—————————–

线段树 定义(百度百科):

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。

线段树至少支持下列操作:

Insert(t,x):将包含区间 int 的元素 x 插入到树t中;

Delete(t,x):从线段树 t 中删除元素 x;

Search(t,i):返回一个指向树 t 中元素 x 的指针。

右图为区间在[1,5]内的线段树

—————————-

线段树用途:

RMQ,线段求长,矩形交,矩形并等……

线段树基本操作:

建树,插入,删除,查询,更新,删树

 线段树的性质:

1, 线段树是平衡的2叉树,最大深度logn(n为线段树所表示区间的长度).
2, 任意的线段[a,b]在线段树的查询或查找过程中把这个线段最多分成log(b-a)份.
3, a[i]的左儿子是a[2*i]、右儿子是a[2*i+1];
以上2条性质保证了线段树除建树外的操作都是log(n)级别的复杂度。

因为它是一棵二叉树,所以它的操作一般除了建树,删树是O(N),其余的都是O(LogN)的。

这个复杂度基本能顺利解决卡时的问题。

—————————–

。。。。。

发表评论