一 背景
在資訊學競賽中，我們經常會碰到一些跟區間有關的問題，比如給一些區
間線段求并區間的長度，或者并區間的個數等等。這些問題的描述都非常簡單，但是通常情況下資料範圍會非常大，而樸素方法的時間複雜度過高，導緻不能在規定時間内得到問題的解。這時，我們需要一種高效的資料結構來處理這樣的問題，在本文中，我們介紹一種基于分治思想的資料結構—-線段樹。
二 簡介
線段樹是一種二叉樹形結構，屬于平衡樹的一種。它将線段區間組織成樹形的結構，并用每個節點來表示一條線段。一棵[1,10)的線段樹的結構如圖1.1所示：
可以看到，線段樹的每個節點表示了一條前閉後開，即[a,b)的線段，這樣表示的好處在于，有時候處理的區間并不是連續區間，可能是離散的點，如數組等。這樣就可以用[a,a＋1)的節點來表示一個數組的元素a，做到連續與離散的統一。
由圖1.1可見，線段樹的根節點表示了所要處理的最大線段區間，而葉節點則表示了形如[a,a+1)的機關區間。對于每個非葉節點（包括根節點）所表示的區間[s,t)，令m = (s + t) / 2，則其左兒子節點表示區間[s,m)，右兒子節點表示區間[m,t)。這樣建樹的好處在于，對于每條要處理的線段，可以類似“二分”的進入線段樹中處理，使得時間複雜度在o(logn)量級，這也是線段樹之是以高效的原因。
三 性質
線段樹具有如下一些性質：
線段樹是一個平衡樹，樹的高度為logn。
線段樹把區間上的任意一條長度為l的線段都分成不超過2logl條線段的并。
線段樹同一層的節點所代表的區間，互相不會重疊。
線段樹任兩個結點要麼是包含關系要麼沒有公共部分, 不可能部分重疊
給定一個葉子p, 從根到p路徑上所有結點代表的區間都包含點p, 且其他結 點代表的區間都不包含點p
線段樹葉子節點的區間是機關長度，不能再分了。
四 基本存儲結構
其中，left 和right分别代表該節點所表示線段的左右端點，即目前節點所表示的線段為[left, right)。而mid = (left + right) / 2，為目前線段的中點，儲存這個點的好處是在每次在目前節點需要對線段分解的時候不需要再計算中點。
這隻是線段樹節點的基本結構，在實際解決問題時，我們需要對應各種題目，在節點中添加各種資料域來儲存有用的資訊，比如添加cover域來儲存目前節點所表示的線段是否被覆寫等等。根據題目來添加适當的資料域以及對其進行維護是線段樹解題的精髓所在，我們在平時的做題中需要注意積累用法，并進行推廣擴充，做到舉一反三。
五 基本操作
5.1 線段樹的建立操作
在對線段樹進行操作前，我們需要建立起線段樹的結構。我們使用結構體數組來儲存線段樹，這樣對于非葉節點，若它在數組中編号為num，則其左右子節點的編号為2*num ，2*num + 1。由于線段樹是二分的樹型結構，我們可以用遞歸的方法，從根節點開始來建立一棵線段樹。代碼如下所示：
對應不同的題目，我們會線上段樹節點中添加另外的資料域，并随着線段的插入或删除進行維護，要注意在建樹過程中将這些資料域初始化。
5.2 線段樹的插入操作
為了在插入線段後，我們能知道哪些節點上的線段被插入（覆寫）過。我們需要在節點中添加一個cover域，來記錄目前節點所表示的線段是否被覆寫。這樣，在建樹過程中，我們需要把每個節點的cover域置0；
如圖1.2所示，線上段的插入過程中，我們從根節點開始插入，同樣采取遞歸的方法。如果插入的線段完全覆寫了目前節點所代表的線段，則将目前節點的cover 域置1并傳回。否則，将線段遞歸進入目前節點的左右子節點進行插入。代碼如下:
要注意，這樣插入線段時，有可能出現以下這種情況，即先插入線段[1,3)，再插入線段[1,5)，如圖1.3所示。這樣，代表線段[1,3)的節點以及代表線段[1,5)的節點的cover值均為1，但是在統計時，遇到這種情況，我們可以隻統計更靠近根節點的節點，因為這個節點所代表的線段包含了其子樹上所有節點所代表的線段。
5.3 線段樹的删除操作
線段樹的删除操作跟插入操作不大相同，因為一條線段隻有被插入過才能被删除。比如插入一條線段[3,10)，則隻能删除線段[4,6)，不能删除線段[7,12)。當删除未插入的線段時，操作傳回false值。
我們一樣采用遞歸的方法對線段進行删除，如果目前節點所代表的線段未被覆寫，即cover值為0，則遞歸進入此節點的左右子節點進行删除。如果目前節點所代表的線段已被覆寫，即cover值為1，則要考慮兩種情況。一是删除的線段完全覆寫目前節點所代表的線段，則将目前節點的cover值置0.由于我們在插入線段的時候會出現圖1.3所示的情況， 是以我們應該遞歸的在目前節點的子樹上所有節點删除線段。另一種情況是删除的線段未完全覆寫目前節點所代表的線段，比如目前節點代表的線段為[1,10)，而要删除的線段為[4,7)，則删除後剩下線段[1,4)和[7,10)，我們采用的方法是，将目前節點的cover置0，并将其左右子節點的cover置1，然後遞歸的進入左右子節點進行删除。
相對插入操作，删除操作比較複雜，需要考慮的情況很多，稍有不慎就會出錯，在比賽中寫删除操作時務必聯系插入操作的實作過程，仔細思考，才能避免錯誤。
5.4 線段樹的統計操作
對應不同的問題，線段樹會統計不同的資料，比如線段覆寫的長度，線段覆寫連續區間的個數等等。其實作思路不盡相同，我們以下以統計線段覆寫長度為例，簡要介紹線段樹統計資訊的過程。文章之後的章節會講解一些要用到線段樹的題目，并會詳細介紹線段樹的用法，以及各種資訊的統計過程。
對于統計線段覆寫長度的問題，可以采用以下的思路來統計資訊，即從根節點開始搜尋整棵線段樹，如果目前節點所代表的線段已被覆寫，則将統計長度加上目前線段長度。否則，遞歸進入目前節點的左右子節點進行統計。實作代碼如下：
完整代碼
六 分類
（1）單點更新
最基礎的線段樹,隻更新葉子節點,然後回溯更新其父親結點。
[hdu][線段樹]1166.敵兵布陣
[hdu][線段樹]1754.i hate it
（2）成段更新
需要用到延遲标記(或者說懶惰标記),簡單來說就是每次更新的時候不要更新到底,用延遲标記使得更新延遲到下次需要更新or詢問到的時候。
（3）區間合并
這類題目會詢問區間中滿足條件的連續最長區間,是以回溯的時候需要對左右兒子的區間進行合并。
（4）掃描線
這類題目需要将一些操作排序,然後從左到右用一根掃描線(當然是在我們腦子裡)掃過去。