ダブリング - sataniC++

概要 「個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。 使える状況 「ある要素に対してその次の要素は容易に得られるが、個分次の要素を得るクエリが時間じゃ間に合わない」 というときに、ダブリングを使うことによって、全体の大きさに対して準備、クエリで求めることが出来ます。 説明 「使える状況」で述べた場面は、具体的には、 ある数の乗を求めたい 根付き木において、ある頂点vの個上の親を知りたい などです。 どちらも、次の要素（や頂点vの親）は容易に求められますね。 しかし、次の次の次の…と初めの要素から個次の要素を知るには、単純に考えると時間がかかってしまいます。 これを時間で行うことが出来るのが、ダブリングと呼ばれる手法です。 ダブリングは、次のような流れで行います。 まずは各要素における「つ次の要素」を調べておきます。 こうすることで、「「つ次の要素」のつ次の要素」、つ

[sh19910711]

LCAでビットごとに見てるのはこれか