最小共通祖先 [いかたこのたこつぼ]
Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると生物進化方面の用語が混じって出てくるので記事をやや探しづらい。 根付き木において、頂点 $a$ と頂点 $b$ を根に向かって辿っていった時、最初に合流する頂点のことを指す。 １ / \ ２ ３ ５と６のLCAは２ / \ ４ ５ ３と４のLCAは１ ｜ ６ １と２のLCAは１ 元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。（追加で前計算する情報が必要になる場合がある）
ダブリング - sataniC++
概要 「個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。 使える状況 「ある要素に対してその次の要素は容易に得られるが、個分次の要素を得るクエリが時間じゃ間に合わない」 というときに、ダブリングを使うことによって、全体の大きさに対して準備、クエリで求めることが出来ます。 説明 「使える状況」で述べた場面は、具体的には、 ある数の乗を求めたい 根付き木において、ある頂点vの個上の親を知りたい などです。 どちらも、次の要素（や頂点vの親）は容易に求められますね。 しかし、次の次の次の…と初めの要素から個次の要素を知るには、単純に考えると時間がかかってしまいます。 これを時間で行うことが出来るのが、ダブリングと呼ばれる手法です。 ダブリングは、次のような流れで行います。 まずは各要素における「つ次の要素」を調べておきます。 こうすることで、「「つ次の要素」のつ次の要素」、つ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
