エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
前処理O(n)クエリO(1)のLCAと静的RMQ - ジョイジョイジョイ
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
前処理O(n)クエリO(1)のLCAと静的RMQ - ジョイジョイジョイ
時間計算量 <O(n), O(1)> の LCA(Lowest Common Ancestor) と RMQ(Range Minimum Query) を C++ で実装... 時間計算量 <O(n), O(1)> の LCA(Lowest Common Ancestor) と RMQ(Range Minimum Query) を C++ で実装しました。 アルゴリズムの解説はDさんのスライド [1] LCA and RMQ ~簡潔もあるよ!~ がとても分かりやすいのでそちらを参照してください。 概要だけ説明します。 LCA の概要 LCA は頂点を dfs 順で訪れた順に並べると深さの列の RMQ に帰着されます。このことは [2] 蟻本 などに載っています。 この列は隣り合う数の差がちょうど になっています。 この列を 個ずつのブロックに分け、それぞれのブロック内の最小値を求めます。 ブロックの数は 個になるので、ブロックの区間の最小値を求めるクエリは sparse table を使うと前処理 、クエリ で処理できます。 ブロックの中についてですが、各ブロック