區間樹

區間樹是在紅黑樹基礎上進行擴展得到的支持以區間為元素的動態集合的操作，其中每個節點的關鍵值是區間的左端點。

區間樹

通過建立這種特定的結構，可是使區間的元素的查找和插入都可以在O(lgn)的時間內完成 。

相比於基礎的數據結構，增加了一個max[x]，即以x為根的子樹中所有區間的端點的最大值。區間樹如下圖所示：

區間樹

這裡的區間查找的並不是精確查找，而是查找和給定區間重疊的元素，重疊的定義如下圖所示：

區間樹

圖中(a)表示兩個區間重疊的情況，其他的(b)、(c)表示沒有重疊的情況。

區間查找

實現INTERVAL-SEARCH(T, i)，返回一個和區間i重疊的區間，若無，則返回nil[T]。基本思想是我們通過左子樹的max進行劃分：如果左子樹的max值小於low[i]，則左子樹不存在這樣的區間和i重疊，轉到右子樹；否則，轉到右子樹，因為左子樹的端點小於右子樹，若左子樹無可能，右子樹也必然不可能。