セグメントツリー

コンピュータサイエンスにおいて、セグメントツリーは、間隔またはセグメントに関する情報を格納するために使用されるデータ構造です。これにより、格納されているセグメントのどれに特定のポイントが含まれているかを照会できます。同様のデータ構造に、間隔ツリーがあります。

n個の区間の集合IのセグメントツリーはO ( nlogn )のストレージを使用し、 O ( nlogn )の時間で構築できます。セグメントツリーは、クエリポイントを含むすべての区間をO (logn + k )の時点で検索することをサポートします。kは取得された区間またはセグメントの数です。^[1]

セグメント ツリーの応用分野は、計算幾何学、地理情報システム、機械学習などです。

セグメント ツリーは、より高次元の空間に一般化できます。

I を区間またはセグメントの集合とします。p 1 、 p 2 _、 ... 、_p mを_、左から右に並べられた異なる区間の端点のリストとします。これらの点によって誘導される実数の直線の分割を考えます。この分割の領域は基本区間と呼ばれます。したがって、基本区間は左から右に次のようになります。

${\displaystyle (-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],\dots ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )}$

つまり、基本区間のリストは、2つの連続する端点p _iとp _{i +1}の間の開区間と、1つの端点からなる閉区間が交互に並んでいるものから構成されます。クエリに対する回答は、基本区間の内部とその端点では必ずしも同じではないため、単一の点は区間として扱われます。^[2]

区間またはセグメントのセットIが与えられた場合、 Iのセグメント ツリーT は次のように構造化されます。

• T は二分木です。
• その葉は、I内の端点によって誘導される基本区間に順序どおりに対応します。最も左の葉は最も左の区間に対応し、以下同様です。葉vに対応する基本区間は Int( v )と表されます。
• Tの内部ノードは、基本区間の和集合 である区間に対応します。つまり、ノードNに対応する 区間 Int( N ) は、 Nをルートとするツリーの葉に対応する区間の和集合です。つまり、 Int( N ) は、その 2 つの子の区間の和集合です。
• T内の各ノードまたはリーフv は、区間 Int( v ) と区間の集合を何らかのデータ構造に格納します。このノードvの正規のサブセットには、 Iからの区間 [ x , x′ ] が含まれますが、[ x , x′ ] には Int( v ) が含まれ、Int(parent( v ) )は含まれません。つまり、T内の各ノードは、その区間にまたがるが親の区間にまたがらないセグメントを格納します。^[3]

セグメントの集合Iからのセグメントツリーは、次のように構築できます。まず、 I内の区間のエンドポイントがソートされます。そこから基本区間が取得されます。次に、基本区間上にバランスのとれたバイナリツリーが構築され、各ノードvについて、それが表す区間 Int( v ) が決定されます。残っているのは、ノードの標準サブセットを計算することです。これを実現するには、 I内の区間をセグメントツリーに 1 つずつ挿入します。区間X = [ x , x′ ] は、次の手順を使用して、 Tをルートとするサブツリーに挿入できます。^[4]

• Int( T )がXに含まれている場合は、 XをTに格納して終了します。
• それ以外：
  • X がTの左の子の区間と交差する場合は、その子にX を再帰的に挿入します。
  • X がTの右の子の区間と交差する場合は、その子にX を再帰的に挿入します。

完全な構築操作にはO ( n log n ) 時間がかかります。n はI内のセグメントの数です。

セグメント ツリーのクエリは、ポイントq _x (ツリーのリーフの 1 つ) を受け取り、ポイントq _{x を}含む格納されているすべてのセグメントのリストを取得します。

正式には、ノード（サブツリー）vとクエリポイントq _xが与えられた場合、次のアルゴリズムを使用してクエリを実行できます。

1. I ( v )内のすべての区間を報告してください。
2. vがリーフでない 場合:
   • q _{x が}Int( vの左の子) にある場合、
     • vの左の子でクエリを実行します。
   • q _{x が}Int( vの右の子) にある場合、
     • vの右の子でクエリを実行します。

n 個の間隔を含むセグメント ツリーでは、特定のクエリ ポイントを含む間隔はO (log n + k ) 時間でレポートできます。ここで、 k はレポートされる間隔の数です。

n 個の間隔のセットI上のセグメント ツリーT は、 O ( n log n ) 個のストレージを使用します。

集合Iには最大4n +1個の基本区間がある。Tは最大4n +1個の葉を持つ二分木なので、その高さはO( log n )である。任意の区間は木の特定の深さで最大2回格納されるため、格納量の合計はO ( nlogn )である。^[5]

セグメント ツリーは、マルチレベル セグメント ツリーの形式で、より高次元の空間に一般化できます。より高次元のバージョンでは、セグメント ツリーは軸平行 (ハイパー) 長方形のコレクションを格納し、指定されたクエリ ポイントを含む長方形を取得できます。この構造はO ( n log ^d n ) のストレージを使用し、O (log ^d n ) 時間でクエリに応答します。

フラクショナルカスケーディングを使用すると、クエリ時間の制限が対数係数で低減されます。関連構造の最​​深レベルで間隔木を使用すると、ストレージの制限が対数係数で低減されます。^[6]

与えられた点を含むすべての区間を尋ねるクエリは、しばしばスタビングクエリと呼ばれます。^[7]

セグメントツリーは、 1次元の範囲クエリでは間隔ツリーよりも効率が悪い。これは、間隔ツリーのO ( n )に対して、セグメントツリーはO ( nlogn )と、より高いストレージ要件を必要とするためである。セグメントツリーの重要性は、各ノードの標準サブセット内のセグメントを任意の方法で格納できることである。^[7]

端点が小さな整数範囲（例えば、[1,..., O ( n )]の範囲）にあるn個の間隔の場合、特定のクエリポイントを含む すべてのk個の間隔を報告するための線形前処理時間とクエリ時間O (1+ k )で最適なデータ構造^{[ which? ]が存在します。}

セグメントツリーのもう1つの利点は、カウントクエリに簡単に適応できることです。つまり、セグメント自体を報告するのではなく、特定のポイントを含むセグメントの数を報告することができます。正規サブセットに間隔を格納する代わりに、単にそれらの数を格納することができます。このようなセグメントツリーは線形ストレージを使用し、O（log n）のクエリ時間を必要とするため、最適です。^[8]

区間木と優先探索木の高次元バージョンは存在しない。つまり、これらの構造を高次元で類似の問題を解決する明確な拡張はない。しかし、これらの構造はセグメント木の関連構造として使用できる。^[6]

セグメントツリーは、 1977年にジョン・ベントレーによって「クレーの長方形問題の解法」の中で発明されました。^[7]

• デ・バーグ、マーク。マーク・ヴァン・クレフェルト。オーヴァーマーズ、マーク。シュワルツコップ、オトフリート (2000)。 「その他の幾何学的データ構造」。計算幾何学: アルゴリズムとアプリケーション(第 2 版)。シュプリンガー・フェルラーク・ベルリン・ハイデルベルク・ニューヨーク。土井：10.1007/978-3-540-77974-2。ISBN 3-540-65620-0。
• http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

• セグメントツリー – CP アルゴリズム