2. ERATO若手輪読会 2014/11/19 • LCA: Lowest Common Ancestor (最近共通祖先) • 根付き木 T 上の2頂点 u, v に対するクエリ LCA(u,v) • u と v の祖先であって、もっとも深い頂点 x を返す • RMQ: Range Minimum Query (区間最小値) • 列 A[1:n] 上の区間 [l, r] に対するクエリ RMQ(l,r) • A[l:r] 中での最小値 A[i] を取るような i を返す • LCA と RMQ には密接な関係がある LCAとRMQ 2 u v x id 1 2 3 4 5 6 A[id] 1 8 2 6 3 5 l r i T