区間木
以上のように構築されたデータ構造があるとき、区間または点についてのクエリを与えられると、その入力とオーバーラップする全ての区間の集合を返す。
区間 R が入力として与えられたとき、それを点を入力として与えられた場合に還元することができる。まず、始点か終点が R の区間内にある区間を全て探す。1次元の場合、各区間の始点と終点で構成された単純な木構造を使えばよい。このとき、各点には対応する区間へのポインタを付与しておく。
この O(log n) の探索によって、考慮すべき最小と最大の点が明らかとなる。この範囲内の各点には区間が対応していて、それがクエリの区間とオーバーラップしているので、解に加える。ただし、始点も終点も R に含まれる区間も考えられるので、二重に登録しないよう注意が必要である。これを防ぐには、各区間を表すデータ構造にフラグを用意しておいて、解に加えられたときにそのフラグを立てればよい。
以上でまだ考慮されていない区間は、R が完全に含まれてしまうような区間である(始点も終点も R の中にはない)。このような区間を探すには、R 内の任意の点について下記に示す点クエリのアルゴリズムを実施すればよい(ここでも、二重に登録しないよう注意が必要である)。
この木構造を高次元に拡張するには、木の各レベルで対応する次元を周期的に変化させればよい。例えば、2次元の場合、奇数レベルではX軸の範囲を扱い、偶数レベルではY軸を扱う。ただし、このような木構造で木の回転によって平衡を保つアルゴリズムは、あまり明らかではない。