Lowest Common Ancestor - Library Checker #196179 解析

nullchilly による Lowest Common Ancestor の Fastest 提出 #196179 を解析する。

ソースコードのコメントを見れば、アルゴリズムは #191763 (pajenegod より)、 RMQ の実装は #177420 (andyli より)と共通であることがわかる。

dp を介する計算は、 1. 部分木サイズ引く 1 の計算 (L89-92) , 2. オイラーツアーの行きがけ順に変換 (L94-97) の 2 段階になっている。

LCA( a[l], a[r] ) = LCA( LCA(a[l],a[l+1]), LCA(a[l+1],a[l+2]), ... , LCA(a[r-1],a[r]) ) ($ l \neq r)

LCA( a[l], a[r] ) はオイラーツアー上の頂点の深さの argmin で計算できる

LCA( a[i], a[i+1] ) = parent( a[i+1] ) (see L101)

より、 RMQ への変換の正当性を確認できる。

RMQ は、短い区間 ( $ B=\log N 程度) は愚直、それ以上は要素数 $ \approx N/Bのスパーステーブルで処理している。これにより

クエリ毎定数時間を求めないことによる高速な構築

セグメント木よりも効率的なメモリアクセス

が実現されていると推測される。