8

私が対処できない問題を見つけたとき、私はテストのために学んでいました：

次の3つの操作を提供する（閉じた）間隔を処理するためのデータ構造を設計します。

Insert（x、y）-間隔を追加[x、y]

Remove（x、y）-間隔[x、y]を削除します

Count（x、y）-間隔[x、y]内に純粋に含まれる間隔の数をカウントします

x、yは1からnまでの整数です。すべての操作には、最大でO（（log n）2）の時間がかかります。

誰か助けてもらえますか？

4

4 に答える 4

4

これは、フェンウィック ツリーと、各ノード内に内部ツリーを格納するセグメント ツリーに基づくデータ構造の組み合わせを使用して、O(log^2 n) 時間と O(nlog n) 空間で解決できます。前者は、指定された範囲内のポイントの数を効率的に見つけて更新するために使用されます。後者は、特定のポイントにまたがるセグメントの数を効率的に見つけて更新するためのものです。基本的な考え方は、指定されたクエリ範囲内のセグメント エンドポイントをカウントし、いずれかまたは両方のエンドポイントをまたぐセグメントを調整することです。

このアルゴリズムは、特定のクエリ範囲 (a, b) に対して、

nContained = (h - nStraddlingOne) / 2

ここで、nContained は (a, b) に含まれる間隔の数、h は (a, b) のいずれかの種類 (開始または終了) の間隔エンドポイントの数、nStraddlingOne は a または b のみを含む間隔の数です。 bのみ。任意の時間間隔の「データベース」は、ここでは D と呼ばれます。

フェンウィック ツリーを使用すると、O(n) テーブルを使用して、O(log n) 時間で 2 つの整数インデックス (a、b) 間のポイントの総数をカウントできます。また、O(log n) 回の挿入と削除が可能です。すべての間隔の両方の終点をそれに追加し、それを使用して O(log n) 時間で h を計算します。

交差を数える

他のデータ構造はセグメント ツリーに非常に似ていますが、主な違いが 2 つあります。間隔の入力セットから間隔の開始点と終了点を推測する代わりに、エンドポイントのセットを 1 から 1 の間のすべての可能な整数にします。 n を含み、「オープン セット」はありません (これは、後で新しい間隔を簡単に追加できるようにするためです)。そして、各ノードの間隔セットを特定の方法で保存します。

簡単にするために、n が 2 の累乗であると仮定します (そうでない場合は、次に大きい 2 の累乗を選択してください。これにより、増加が n 未満になるため、時間の計算量は変わりません)。T を、位置 1 <= i <= n ごとにリーフ ノードを持つ完全な二分木とします。(このツリーには合計 2n - 1 個のノードがあります。) 各リーフ ノードは 1 つの位置を表します。すべての非葉ノードは、その下にあるすべての葉ノードの位置の和集合を表し、長さが 2 のべき乗の間隔を形成する必要があります。ノード v Int(v) で表される間隔を呼び出します。(注: このバイナリ ツリーは完全であるため、スペースを節約するために、バイナリ ヒープと同じように「暗黙的に」表すことができます。)

T の各ノード v には、Span(v) と呼ばれる間隔のセットが対応しています。(実際には、最も右側のエンドポイントのみを格納します。) Span(v) は、D 内のすべての間隔のセットです。

  1. Int(v)を含み、かつ
  2. Int(parent(v)) を含めないでください。

各頂点 v では、間隔の右端の端点のみを Span(v) に格納します。この端点によって順序付けられ、すべてのノードが子孫ノードの数で拡張され た自己平衡バイナリ ツリーに格納されます。つまり、「外側」ツリーのすべてのノードには「内側」ツリーが含まれます。 これは、特定のクエリ間隔を完全に含む間隔の数を効率的に計算できるようにするために必要です。

セグメント ツリーでの基本的なクエリ操作は、特定の点 x を含む間隔のセットを決定することです。これは、個々の間隔を報告するのではなく、カウントするように簡単に変更できます。操作は簡単です: v をルートに設定し、

  1. Span(v) の間隔の数を合計に追加します。
  2. v が葉の場合、停止します。
  3. それ以外の場合、v の左と右の子がそれぞれ u と w であるとします。x が Int(u) に含まれている場合は u で再帰し、そうでない場合は w で再帰します。

クエリ間隔 (a, b) を指定すると、上記のクエリは、a に対して 1 回、b に対して 1 回、合計 2 回実行できます。nStraddlingAtLeastOne を両方のクエリのカウントの合計に設定します。カウントは各ノードに対して O(1) 時間で実行できることに注意してください。これは、Span(v) を格納する自己平衡バイナリ ツリーのルート ノードのカウント フィールドにすぎません。

ダブルクロス！

困難 (そして、私が時間を費やした O(log n) アルゴリズムの以前の試みを最終的に妨げたもの) は、クエリの両方のエンドポイント (a、b) に同時にまたがる間隔の数もカウントする必要があることです。これを行うには、再びルートの v から開始し、a (クエリの開始点) に対して変更されたクエリを実行します。ここで、ステップ 1 は次のように置き換えられます。

  1. 右端点 >= b を持つ Span(v) の間隔の数をカウントし、合計に追加します。

このカウント手順は、自己平衡バイナリ ツリーにより、O(log n) 時間で実行できます。各ツリー レベルには最大 2 つのカウント操作が必要であるため、これは時間の複雑さを O(log^2 n) まで押し上げる部分です。nContaining をこのクエリの合計に設定します。を使用してnStraddlingOneを計算できます

nStraddlingOne = nStraddlingAtLeastOne - nContaining

nStraddlingOne とフェンウィック ツリーから計算された h を使用して、上の式に従って nContained を計算できるようになりました。

間隔の追加と削除

フェンウィック ツリーの更新は O(log n) であるため、更新も O(log^2 n) であり、間隔 (x, y) をセグメント ツリーに追加するには、次のアルゴリズムを使用すると O(log^2 n) の時間がかかります。ルートで v から開始します。

  1. (x, y) に Int(v) が含まれる場合、Span(v) の右端点を格納する自己平衡二分木に y を追加して停止します。
  2. それ以外の場合、v の左と右の子がそれぞれ u と w であるとします。
    • (x, y) が Int(u) とオーバーラップする場合、u を再帰します。
    • (x, y) が Int(w) とオーバーラップする場合、w で再帰します。

上記のトラバーサルは、セグメント ツリー内の O(log n) ノードのみを訪問します。これは、追加された各間隔が、任意のツリー レベルで最大 2 つのノードの間隔セットに表示され、間隔ごとに最大 2log(n) のスペース使用量になるためです。証拠と詳細な説明については、セグメント ツリーのウィキペディアのページを参照してください。間隔を削除するには、同様のアルゴリズムを使用します。ノードで自己平衡二分木に挿入または削除するたびに、合計で O(log^2 n) 時間、O(log n) 時間がかかります。

スペース利用

セグメント ツリーには O(log n) 個のツリー レベルがあり、それぞれの可能なエンドポイントを含む内部ツリー ノードの 2 つのインスタンス用のスペースが必要な場合があるため、スペースの使用量は O(nlog n) です。特に、O(n^2) 個の間隔が存在する可能性がありますが、各間隔の右端のみを保存するため、これは問題ではないことに注意してください。また、カウントを保存するため、既存の間隔の 2 番目のコピーを追加しても、カウントが増えるだけで、新しいノードの割り当ては発生しません。フェンウィック ツリーは O(n) 空間のみを使用します。

于 2012-12-12T16:47:18.633 に答える
1

範囲ツリーを参照してください。クエリの時間計算量は、O(log d n + k) と表されます。ここで、d は次元、n はツリーに格納されているポイントの数、k はクエリによってレポートされるポイントの数です。

ただし、ポイントを報告せずにカウントのみが必要です。したがって、各ノードで子の数（実際には葉に実際の点が格納されているため葉の数）が維持されている場合、この k を削除して O(log 2 n) を残すことができると思います。挿入も削除もO(log 2 n)です。

于 2012-12-12T08:33:29.510 に答える
0

区間木はここに収まります。たとえば、https：//github.com/ekg/intervaltree/blob/master/IntervalTree.hこのコードを参照してください。これは、O（log（n））に見えるfindContainedを提供します。より複雑ですが、確実にO（log（n）） http://en.wikipedia.org/wiki/Interval_tree#Deletionで実行できます。

于 2012-12-12T05:07:56.643 に答える