セグメントツリー

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

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

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

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

意味

説明

$I を$ 区間、あるいは線分の集合とする。p 1 、_p2 _、 …、p _mを、左から右に並べられた、異なる区間の端点のリストとする。これらの点によって誘導される実数直線の分割を考える。この分割領域は基本区間と呼ばれる。したがって、基本区間は左から右に以下のようになる。

(-\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}の間の開区間と、単一の端点からなる閉区間が交互に並んだものから構成される。単一点は、クエリに対する答えが基本区間の内部とその端点において必ずしも同じとは限らないため、それ自体が区間として扱われる。^{[ 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の各ノードは、自身の区間をまたぐが親の区間をまたがらない線分を格納する。^[³^]

工事

線分集合 $Iから線分木を構築するには、次のようにする。まず、$ $I$ 内の区間の端点をソートする。そこから基本区間を求める。次に、基本区間上にバランスのとれた二分木を構築し、各ノードvについて、それが表す区間 Int( v ) を求める。最後に、各ノードの正規部分集合を計算する。これを実現するために、 $I$ 内の区間を一つずつ線分木に挿入する。区間X = [ x , x′ ] は、以下の手順でTを根とする部分木に挿入できる。^{[ 4 ]}

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

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

証拠

エンドポイントのソートにはO ( n log n ) の時間がかかります。ソートされたエンドポイントからバランスの取れた二分木を構築するには、nに対して線形時間がかかります。

区間X = [ x , x′ ]をツリーに挿入するには、O(log n )のコストがかかります。

証拠

すべてのノードを訪問するには定数時間かかります（標準部分集合がリンクリストのような単純なデータ構造に格納されていると仮定）。ノードvを訪問すると、X がvに格納されるか、 Int( v ) にXのエンドポイントが含まれます。上で証明したように、ツリーの各レベルで区間は最大2回格納されます。また、各レベルには、対応する区間に x が含まれるノードが最大で1つあり、区間にx′が含まれるノードが1つあります。したがって、レベルごとに最大4つのノードが訪問されます。O (log n ) レベルあるため、挿入の総コストはO (log n ) です。^[¹^]

クエリ

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

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

$I (v)$ 内のすべての区間を報告してください。
vがリーフでない場合:
- q _xが Int( vの左の子) にある場合、
  - vの左の子でクエリを実行します。
- q _xが Int( vの右の子) にある場合、
  - vの右の子でクエリを実行します。

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

証拠

クエリアルゴリズムはツリーの各レベルにつき1つのノードを訪問するため、合計でO (log n )個のノードを訪問する。一方、ノードvでは、 $I$ 内のセグメントはO (1 + k _v )回で報告される。ここで、 k _vはノードvで報告される区間の数である。訪問されたすべてのノードvにおけるk _vの合計は、報告されるセグメントの数であるkである。 ^[⁵^]

ストレージ要件

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

補題- $I$ の任意の区間[ x、 x′ ]は、同じ深さにある最大2つのノードの標準セットに格納されます。

証拠

v ₁、v ₂、v ₃を、左から右に番号が付けられた同じ深さの 3 つのノードとし、 p( v )を任意のノードvの親ノードとします。 [ x、x′ ] がv ₁とv ₃に格納されているとします。これは、[ x、x′ ] が Int( v ₁ )の左端からInt( v ₃ )の右端までの全区間に及ぶことを意味します。特定のレベルのすべてのセグメントは重複せず、左から右の順序になっていることに注意してください。これは、リーフを含むレベルの構築によって真であり、隣接するセグメントのペアを組み合わせることによって任意のレベルからその上のレベルに移動しても、このプロパティは失われません。これで、parent( v ₂ ) = parent( v ₁ ) であるか、前者が後者の右側にあるか (ツリー内のエッジは交差しない) のいずれかになります。最初のケースでは、Int(parent( v ₂ )) の左端の点は Int( v ₁ ) の左端の点と同じです。2 番目のケースでは、Int(parent( v _{2 )) の左端の点は Int(parent(}v ₁ ))の右端の点の右側にあり、したがって Int( v ₁ ) の右端の点の右側でもあります。どちらのケースでも、Int(parent( v _{2 )) は Int(}v ₁ ) の左端の点またはその右側で始まります。同様の推論から、Int(parent( v _{2 )) は Int(}v ₃ )の右端の点またはその左側で終わることがわかります。したがって、Int(parent( v _{2 )) は [}x、x′ ]に含まれている必要があります。したがって、[ x、x′ ] はv ₂に格納されません。

集合

I

は最大で4 n + 1個の基本区間を持つ。Tは最大で4 n + 1個の葉を持つ二分均衡木であるため、その高さはO(log n )である。任意の区間は木の特定の深さに最大で2回格納されるため、総記憶容量はO ( n log n )である。^{[ 5 ]}

高次元への一般化

セグメント木は、多段セグメント木の形で高次元空間に一般化できます。高次元バージョンでは、セグメント木は軸平行（超）長方形の集合を格納し、指定されたクエリ点を含む長方形を検索できます。この構造はO ( n log ^d n )のストレージを使用し、 O ( log ^d n )の時間でクエリに応答します。

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

注記

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

セグメント木は、1次元の範囲クエリにおいては、区間木よりも効率が悪い。これは、区間木のO ( n )に対して、セグメント木はO ( nlogn )という高い記憶容量を必要とするためである。セグメント木の重要性は、各ノードの正規部分集合内のセグメントを任意の方法で格納できることである。^[⁷^]

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

セグメントツリーのもう一つの利点は、カウントクエリに容易に適応できることです。つまり、セグメント自体を報告するのではなく、特定の点を含むセグメントの数を報告することができます。正規部分集合に区間を格納する代わりに、単にその数を格納するだけで済みます。このようなセグメントツリーは線形記憶を使用し、O (log n ) のクエリ時間を必要とするため、最適です。^{[ 8 ]}

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

歴史

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

参考文献

^ ^a ^b ( de Berg et al. 2000 , p. 227)
^ ( de Berg et al. 2000 , p. 224)
^ ( de Berg et al. 2000 , pp. 225–226)
^ ( de Berg et al. 2000 , pp. 226–227)
^ ^a ^b ( de Berg et al. 2000 , p. 226)
^ ^a ^b ( de Berg et al. 2000 , p. 230)
^ ^a ^b ^c ( de Berg et al. 2000 , p. 229)
^ ( de Berg et al. 2000 , pp. 229–230)

引用元

デ・バーグ、マーク。マーク・ヴァン・クレフェルト。オーヴァーマーズ、マーク。シュワルツコップ、オトフリート (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アルゴリズム

[Schwarzkopf1-1] ( de Berg et al. 2000 , p. 227)

[2] ( de Berg et al. 2000 , p. 224)

[3] ( de Berg et al. 2000 , pp. 225–226)

[4] ( de Berg et al. 2000 , pp. 226–227)

[Schwarzkopf2-5] ( de Berg et al. 2000 , p. 226)

[Schwarzkopf3-6] ( de Berg et al. 2000 , p. 230)

[Schwarzkopf4-7] ( de Berg et al. 2000 , p. 229)

[8] ( de Berg et al. 2000 , pp. 229–230)

[

[ 2 ]

[

[ 4 ]

[

[ 6 ]

[ 7 ]

[ 8 ]