線段樹，也叫區間樹，是一個完全二叉樹，它在各個節點儲存一條線段（即“子數組”），因而常用于解決數列維護問題，基本能保證每個操作的複雜度為o(lgn)。
線段樹是一種二叉搜尋樹，與區間樹相似，它将一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。
對于線段樹中的每一個非葉子節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。是以線段樹是平衡二叉樹，最後的子節點數目為n，即整個線段區間的長度。
使用線段樹可以快速的查找某一個節點在若幹條線段中出現的次數，時間複雜度為o(logn）。而未優化的空間複雜度為2n，是以有時需要離散化讓空間壓縮。
線段樹的基本操作主要包括構造線段樹，區間查詢和區間修改。
（1）線段樹構造
首先介紹構造線段樹的方法：讓根節點表示區間[0,n-1]，即所有n個數所組成的一個區間，然後，把區間分成兩半，分别由左右子樹表示。不難證明，這樣的線段樹的節點數隻有2n-1個，是o(n)級别的，如圖：
節點定義如下：
完整的建樹代碼如下:
當在a[i]~a[j]上的所有的元素都加上一個值c的時候
如果a[i]~a[j]剛還是一個完整段的時候，直接将這個段的value值加上c*(r-l+1)
當更新的區間不是一個完整段的時候，采用一種記錄增量的方法：給每個節點增加一個域：int add，記錄更新操作的增量c，初始的時候add均為0，比如當對2~5區間更新後，給該結點的add加上一個值c，再下次要對2~3結點進行更新或查詢時，再将add傳遞到下面的孩子結點中去
完整的更新樹代碼如下:
查詢區間l~r上的value值
<a href="http://poj.org/problem?id=2182" target="_blank">poj2182 lost cows</a>
