實(shí)際上還是稱為區(qū)間樹更好理解一些。
樹：是一棵樹，而且是一棵二叉樹。
線段：樹上的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)線段(還是叫“區(qū)間”更容易理解，區(qū)間的起點(diǎn)和終點(diǎn)通常為整數(shù))
同一層的節(jié)點(diǎn)所代表的區(qū)間，相互不會(huì)重疊。
葉子節(jié)點(diǎn)的區(qū)間是單位長(zhǎng)度，不能再分了。

線段樹是一棵二叉樹，樹中的每一個(gè)結(jié)點(diǎn)表示了一個(gè)區(qū)間[a,b]。a,b通常是整數(shù)。每一個(gè)葉子節(jié)點(diǎn)表示了一個(gè)單位區(qū)間。對(duì)于每一個(gè)非葉結(jié)點(diǎn)所表示的結(jié)點(diǎn)[a,b]，其左兒子表示的區(qū)間為[a,(a+b)/2]，右兒子表示的區(qū)間為[(a+b)/2,b](除法去尾取整）。

線段樹的基本用途：
線段樹適用于和區(qū)間統(tǒng)計(jì)有關(guān)的問題。比如某些數(shù)據(jù)可以按區(qū)間進(jìn)行劃分，按區(qū)間動(dòng)態(tài)進(jìn)行修改，而且還需要按區(qū)間多次進(jìn)行查詢，那么使用線段樹可以達(dá)到較快查詢速度。

線段樹的構(gòu)建

   createSeg   //以節(jié)點(diǎn)v為根建樹、v對(duì)應(yīng)區(qū)間為[l,r]
?{
?    對(duì)節(jié)點(diǎn)v初始化
     if (l!=r)
?    {
?        以v的左孩子為根建樹、區(qū)間為[l,(l+r)/2]
?        以v的右孩子為根建樹、區(qū)間為[(l+r)/2+1,r]
?    }
?}

(瀏覽器似乎不太好用了，上面的代碼點(diǎn)“插入代碼”不管用，就直接貼出來了)

個(gè)人感覺線段樹比較靈活，要多做一些題目才能對(duì)線段樹有一個(gè)大概的掌握。
網(wǎng)上看見了一些線段樹的資料，這里也貼出來。

線段樹的一種簡(jiǎn)化實(shí)現(xiàn) 
http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html

線段樹(區(qū)間樹)Segment Tree

http://www.wutianqi.com/?p=1140

http://www.wutianqi.com/?p=1369

線段樹基礎(chǔ)知識(shí)
http://hi.baidu.com/lemon_cn/blog/item/2093b64bd63797f682025c9f.html

線段樹的構(gòu)造過程
http://kmplayer.javaeye.com/blog/576486

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

數(shù)據(jù)結(jié)構(gòu) – 線段樹
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.shnenglu.com/NicYun/archive/2008/08/05/58037.html

線段樹
http://blog.chinaunix.net/u3/102500/showart_2257428.html

下一篇我會(huì)貼出樹狀數(shù)組的講解。