區間樹

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

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

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

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

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