区間木 - Wikipedia
区間木またはインターバル木︵英: Interval tree︶は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木︵英: Segment tree, segtree︶があるが別物である。 基本的手法[編集] 単純なケースとして、区間が互いにオーバーラップしないなら、単純な2分木で表すことができ、クエリにかかる時間は O(logn) となる。しかし、区間同士がオーバーラップするなら、始点でソートする場合と終点でソートする場合で順序が異なることになるので、挿入時に2つの区間をどう比較すべきかが問題となる。素朴な方法とし
食事する哲学者の問題 - Wikipedia
