データ構造における静的フィンガー定理
静的な指の定理 −fをfingerと呼ばれる特定の要素として扱うようにします。
次に、以下の式は、シーケンスを表示するコストの限界です
O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j
注 − | f-i |指とアイテムiの間のアイテムの対称的な順序での距離として示されます。
ここで、mは、最大n個のノードを持つツリーでの更新またはアクセス操作の数として示されます。
少なくとも償却の意味では、nノードを超えないツリーでの最初のm回の操作にかかる時間は、AVLツリーや2〜3ツリーなどの平衡二分探索ツリーにかかる時間と同じであることに注意してください。
-
データ構造のセグメントツリー
このセクションでは、セグメントツリーとは何かを確認します。それについて説明する前に、1つの問題を見てみましょう。 配列arr[0、…、n-1]があるとすると、次の操作を実行できます- インデックスlからrまでの要素の合計を求めます。ここで0≤l≤r≤n-1 配列の指定された要素の値を新しい値xに変更します。 arr [i]=xを実行する必要があります。 0からn–1の範囲のi。 この問題は、セグメントツリーを使用して解決できます。セグメントツリーは、O（log n）時間で合計とクエリを取得するのに役立ちます。では、これを表現する方法を見てみましょう- リーフノードは、
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ