线段树(区间树)Segment Tree

实际上还是称为区间树更好理解一些。
树:是一棵树,而且是一棵二叉树。
线段:树上的每个节点对应于一个线段(还是叫“区间”更容易理解,区间的起点和终点通常为整数)
同一层的节点所代表的区间,相互不会重叠。
叶子节点的区间是单位长度,不能再分了。

线段树是一棵二叉树,树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b],其左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2,b](除法去尾取整)。

线段树的基本用途:
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分,按区间动态进行修改,而且还需要按区间多次进行查询,那么使用线段树可以达到较快查询速度。

线段树的构建

1
2
3
4
5
6
7
8
9
10

   createSeg   //以节点v为根建树、v对应区间为[l,r]{
    对节点v初始化
     if (l!=r){
        以v的左孩子为根建树、区间为[l,(l+r)/2]
        以v的右孩子为根建树、区间为[(l+r)/2+1,r]}}

个人感觉线段树比较灵活,许啊哦多做一些题目才能对线段树有一个大概的掌握。
网上看见了一些线段树的资料,这里也贴出来。

线段树的一种简化实现 
http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html

线段树基础知识
http://hi.baidu.com/lemon_cn/blog/item/2093b64bd63797f682025c9f.html

线段树的构造过程
http://kmplayer.javaeye.com/blog/576486

RMQ问题以及ST算法
http://hi.baidu.com/wjn123335/blog/item/4d485a08414c5ed362d9868a.html

数据结构 – 线段树
http://www.cnblogs.com/superbin/archive/2010/07/17/1779842.html
http://www.cnblogs.com/superbin/category/253674.html
http://www.cnblogs.com/superbin/archive/2010/08/02/1790467.html

线段树模版
http://www.cppblog.com/NicYun/archive/2008/08/05/58037.html

线段树
http://blog.chinaunix.net/u3/102500/showart_2257428.html

一些线段树题目解答报告:
http://hi.baidu.com/%D2%B9%D3%EA552734199/blog/item/0490979aeb47f3bec8eaf44a.html

http://hi.baidu.com/%D2%B9%D3%EA552734199/blog/category/%CF%DF%B6%CE%CA%F7/index/2

http://www.cnblogs.com/cnjy/archive/2009/08/30/1556566.html

http://hi.baidu.com/ahhygx/blog/item/f5d52c2b120a6f91023bf627.html

http://hi.baidu.com/%C4%BE%D7%D3%C8%D5%D4%C8/blog/item/dd42f8f5267b3063dcc47472.html

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《线段树(区间树)Segment Tree》有3个想法

  1. I can not cease studying this.It really is so nice, so full of information that i simply didn’t know.I am lucky to view that guests are actually talking about this downside in this kind of a intelligent technique, displaying us all many different. You are one great blogger. Please keep it up. I can not wait to go through what’s next.

发表评论

电子邮件地址不会被公开。 必填项已用*标注