区間木
別の手法は、Introduction to Algorithms, Second Editionの 14.3 章(pp.331–317、First Edition は15.3章)に記述がある。
挿入と削除にかかる時間は O(log n) である(n は区間の総数)。
これは、単純な順序木(例えば2分探索木や平衡2分探索木)を使うもので、ノードの順序は各区間の始点(下限の値)に従い、各ノードには区間の終点(上限)とそのノード配下の部分木全体の最大上限値が格納される。この情報を挿入・削除に際して保つには、O(h) ステップ(h はそのノードの高さ)の処理を行えばよく、上位ノードに対して最大値の更新をしていく。
2つの区間 A と B がオーバーラップするのは、A.low ≤ B.high と A.high ≥ B.low が同時に成り立つ場合だけである。この木構造でオーバーラップを探して走査していく場合、以下のような場合を即座に除外できる。
右の子ノードの始点(下限)がクエリの終点(上限)より大きい場合、それ以降の部分木は走査する必要がない。
最大上限値がクエリの始点より小さい部分木は走査する必要がない。
区間は全体としては、まず始点の値でソートされ、次いで終点の値でソートされていることになる。この順序付けを利用して区間の二重登録を防ぐことができる。区間の挿入は O(log n) だが、二重登録の検出には O(k + log n) がかかる(k は新たな区間とオーバーラップしている区間数)。
区間木はより高次の N 次元に拡張でき、クエリ時間と構築時間は1次元と同じで、メモリ使用量は O(n log n) となる。
まず、N次元の領域探索木を構築し、クエリの領域 R に始点や終点が含まれる全ての区間を効率的に検索できるようにする。そのような領域が明らかになったら、残る問題はクエリの領域を内包する領域を探す方法である。そのようなオーバーラップを探すにはN次元の区間木を構築し、いずれかの座標軸について R と交差するかどうかを調べる。例えば、2次元の場合、X軸についての区間木を構築し、四角形などの領域 R がクエリとして与えられる。そして、同時にY軸についての区間木に対しても同様にクエリを処理する。
次元があがると、それに対応して区間木も余分に必要になる。木構造を走査する際に、オーバーラップを探すために x と S_center の比較を行う。1次元の場合に2つのソートされたリストが使われていた部分に、領域探索木を構築する。これにより、S_center と領域 R のオーバーラップを効率的に検索できるようになる。