參考：https://en.wikipedia.org/wiki/Interval_tree
百度很多關于interval tree和segment tree的感覺都有問題，于是去Wikipedia查了一下interval tree，在這裡總結一下。
線段樹用來索引線段，比如時間段[1,10], [3,7], [20,30]，主要支援點查詢，比如查找時間點4，會查出[1,10]和[3,7]，範圍查詢會附加用一顆獨立的樹形結構如B+樹輔助查詢。
有兩種interval tree的實作，這裡介紹其中一種 Centered interval tree
Centered interval tree
Centered interval tree 是一顆三叉樹，專門用來應對點查詢。
給定 n 個線段，用 Ts 和 Te 表示起點和終點。首先确定一個中心點，中心點會把所有線段分成三部分：
a：Te 比 中心點 小的線段集合。
b：中心點 落在[Ts,Te]中間的線段。
c：Ts 比 中心點 大的線段。
a 為目前節點，b 為 a 的左子樹，c 為 a 的右子樹。樹的整體構造過程就是這樣，中心點的選擇盡量使樹平衡。
目前節點維護五個資訊：
1：中心點的值
2：指向左子樹的指針
3：指向右子樹的指針
4：按 Ts 将 a 中的線段排序
5：按 Te 将 a 中的線段排序
下面以 7 條線段為例，給出一個 interval tree 的示意圖（僅表示大概意思）
[1,5]
[2,4]
[6,13]
[7,11]
[8,12]
[17,21]
[18,22]
其中 10 ，3 ，20 是三個節點的中心點。3和20兩顆子樹沒有子節點了。
查詢包含點 p 的線段，從根節點開始，先和第一個節點開始查找，如果 p 等于目前中心點，則直接傳回所有目前節點的線段，不再查找子樹。如果 p 比中心點小，則遞歸查找左子樹，p 比中心點大類似。
目前節點維護的都是覆寫中心點的線段。如果 p 比中心點小，則所有線段的 Te 都比 p 大，隻需要查找第 4 部分（按 Ts 将線段排序），所有小于 p 的 Ts 的線段都會覆寫 p ，滿足查詢條件。
其中x_center為中心點，x為查找的點。下圖是節點内部的查找過程
查詢7.5的示例圖：首先查找根節點，因為7.5比10小，繼續查找左子樹。最後找到兩個線段[6,13], [7,11]。
給定查詢範圍[m, n]，傳回與[m, n] 相交的所有線段。需要一個一維樹形結構輔助。一般用B+樹。
兩條線段相交有四種：其中黑色線段為查詢條件，下邊線段為相交的線段。
這四種可以進一步分為兩種情況：
a，b，c ：左右端點至少有一個在查詢範圍内。
d：完全覆寫查詢範圍。
滿足第一種情況的線段可以通過對所有線段建立一顆 B+ 樹，将每個線段的左右端點插入到樹中。範圍查詢可以直接查找開始節點和結束節點，中間端點連結的線段都滿足要求。
第二種情況可以通過 interval tree來查，從查詢範圍中随便取一個點進行點查詢。
最後進行合并去重。
查詢[7.5, 9]。首先在 B+ 樹中找到滿足第一種情況的線段。
找到線段：[8,12]
再随便取個中間值 7.8 到 interval tree 中找到滿足第二種情況的線段。
找到線段：[6,13], [7,11]
最後合并去重，得到結果集[8,12]，[6,13]， [7,11]