Segment tree とは

コンピュータ科学では、統計木とも呼ばれるセグメントツリーは、区間またはセグメントに関する情報を格納するために使用されるツリーデータ構造です。これは、記憶されたセグメントのうちのどれが所与のポイントを含むかを照会することを可能にする。原則として、静的な構造です。つまり、構築された後は変更できない構造です。同様のデータ構造がインターバルツリーです。
n個の区間からなる集合Iに対するセグメントツリーは、O(n log n)の記憶を使用し、O(n log n)時間で構築することができる。セグメントツリーは、O(log n + k)内のクエリポイントを含むすべての間隔を検索することをサポートし、kは検索された間隔またはセグメントの数である。
セグメントツリーのアプリケーションは、計算幾何学と地理情報システムの分野にあります。
セグメントツリーは、より高い次元の空間に一般化することができる。