joisino https://blog.hatena.ne.jp/joisino/ ｼﾞｮｲｼﾞｮｲｼﾞｮｲ https://joisino.hatenablog.com/ 時間計算量 <O(n), O(1)> の LCA(Lowest Common Ancestor) と RMQ(Range Minimum Query) を C++ で実装しました。 アルゴリズムの解説はDさんのスライド [1] LCA and RMQ ~簡潔もあるよ！~ がとても分かりやすいのでそちらを参照してください。 概要だけ説明します。 LCA の概要 LCA は頂点を dfs 順で訪れた順に並べると深さの列の RMQ に帰着されます。このことは [2] 蟻本 などに載っています。 この列は隣り合う数の差がちょうど になっています。 この列を 個ずつのブロックに分け、それぞれのブロック内… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjoisino.hatenablog.com%2Fentry%2F2017%2F08%2F13%2F210000" title="前処理O(n)クエリO(1)のLCAと静的RMQ - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%201 Hatena Blog https://hatena.blog 2017-08-13 21:00:00 rich https://joisino.hatenablog.com/entry/2017/08/13/210000 1.0 100%