区間木
次に点 x が入力として与えられた場合を考える。通常の2分木を走査するのと同様の再帰的アルゴリズムで木構造を走査する。各ノードについて x とそのノードの中央点である x_center を比較する。x が x_center より小さい場合、左側の S_left を調べる。x が x_center よりも大きい場合、右側の S_right を調べる。
根ノードから葉ノードまで、走査していく過程で、それぞれのノードの S_center に含まれる区間群を処理する。x が x_center より小さい場合、S_center にある区間は必ず終点が x より大きい(そうでないと x_center とオーバーラップできない)。したがって、S_center にある区間群のうち x より始点が小さい区間を探せばよい。S_center に対応するデータ構造はすでにあるのでそれを使い、この場合は始点だけを見ればいいので始点でソートされたリストを調べる。始点が x より小さい区間は、必ず x を含んでいる(終点は x_center より大きく、x_center は x より大きいため)。したがって、始点でソートされたリストを先頭から順に見ていき、始点が x より小さいものを出力に加える(始点が x を超えた時点で終了)。
同様に x が x_center より大きい場合、S_center にある区間群は全て始点が x より小さいことがわかっているので、終点でソートされたリストを使って、終点が x より大きい区間を探せばよい。
x が x_center と同一の場合、S_center にある区間群は全て解に含めることができ、しかもそれ以降の木構造の走査をする必要がない。