差分
この文書の現在のバージョンと選択したバージョンの差分を表示します。
| 両方とも前のリビジョン 前のリビジョン | |||
|
programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/29] ikatakos [EulerTour + RMQ] |
programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/04] (現在) ikatakos [ダブリング] |
||
|---|---|---|---|
| ライン 103: | ライン 103: | ||
| == $a,b$ の深さを合わせる == | == $a,b$ の深さを合わせる == | ||
| - | $b$ の方が深いとし、深さの差が2進数で 100110 だったとする (5,2,1桁目が'1') | + | $b$ の方が深いとし、深さの差が38（2進数で 100110）だったとする。 |
| - | 先頭のbitから頂点を遡っていく | + | 立っているbitだけ頂点を遡っていく。0-indexedで1,2,5桁目が'1'なので、 |
| - | b2 = double[b ][5] | + | b2 = double[b ][1] |
| b3 = double[b2][2] | b3 = double[b2][2] | ||
| - | b4 = double[b3][1] → b4とaで深さが揃った。以降 b = b4 とする | + | b4 = double[b3][5] → これでb4とaで深さが揃った |
| + | |||
| + | 以降 $b$ は $b_4$ のことを指すとする。 | ||
| == 同階層ながら互いに異なる、最も浅い祖先を求める == | == 同階層ながら互いに異なる、最も浅い祖先を求める == | ||
