差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
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$ のことを指すとする
  
 == 同階層ながら互いに異なる、最も浅い祖先を求める == == 同階層ながら互いに異なる、最も浅い祖先を求める ==
programming_algorithm/graph_theory/lowest_common_ancestor.txt · 最終更新: 2019/12/04 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0