データ構造における静的フィンガー定理（Static Finger Theorem）とは
静的フィンガー定理（Static Finger Theorem）とは
静的フィンガー定理は、スプレー木（splay tree）における一連のアクセス操作のコストを評価するための重要な定理です。ここでは、特定の要素 f を「フィンガー」と呼ばれる基準点として扱います。
このとき、m 回の操作からなるシーケンスをスプレーする際のコストは、次の式によって上から抑えられます。
O(m + n log(n) + Σ log(|f − i[j]| + 1))
記号の意味
- |f − i|：フィンガー f と要素 i の間の、対称順（in-order）における距離を表します。
- m：最大 n 個のノードを持つ木に対して実行される更新操作またはアクセス操作の回数です。
- n：木が取りうるノード数の上限です。
平衡二分探索木との比較
注目すべき点として、少なくとも償却解析（amortized analysis）の意味において、ノード数が n を超えない木に対する最初の m 回の操作にかかる時間は、AVL 木や 2-3 木といった平衡二分探索木で必要となる時間と同程度であることが分かります。
つまり、スプレー木は各ノードにバランス情報を保持することなく、償却計算量の観点では平衡二分探索木と同等の性能を発揮できることを、この定理は示しています。アクセス対象がフィンガーの近くに集中している場合には、さらに効率的な動作が期待できます。
-
セグメントツリー（Segment Tree）とは？データ構造の基本と仕組みをわかりやすく解説
セグメントツリーとは セグメントツリー（Segment Tree）は、配列に対する「区間に関する問い合わせ」と「要素の更新」を高速に処理するためのデータ構造です。本記事では、セグメントツリーが必要とされる背景と、その基本的な構成方法について解説します。 解決したい問題 まず、次のような問題を考えてみましょう。長さ n の配列 arr[0 … n-1] が与えられたとき、以下の2つの操作を効率よく行いたいとします。 区間和の取得：インデックス l から r までの要素の合計を求める（0 ≤ l ≤ r ≤ n-1） 要素の更新：指定したインデックス i の値を新しい値 x に変更する（arr
-
ハーフエッジデータ構造（HalfedgeDS）とは？基本概念とCGAL実装例をわかりやすく解説
はじめにテンプレートパラメータとして用いられるハーフエッジデータ構造（Halfedge Data Structure、略称 HalfedgeDS）は、頂点・辺・面の接続情報（インシデンス情報）を管理できる、辺を中心としたデータ構造として定義されています。平面地図（planar map）や多面体など、任意の次元空間に埋め込まれた向き付け可能な2次元曲面の表現に適した構造です。このデータ構造では、各辺が逆向きの向きを持つ2つのハーフエッジ（半辺）に分割されます。各ハーフエッジは、隣接する1つの面と1つの頂点への参照を保持し、逆に各面および各頂点にも、それぞれ1つの接続ハーフエッジが格納されます。さ