エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
HL decomposition+SegTreeのlogを1個消す - よすぽの日記
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
HL decomposition+SegTreeのlogを1個消す - よすぽの日記
はじめに この記事はHL分解について書きます。 HL分解+SegTreeでパス上のクエリに答えると、最悪ケース... はじめに この記事はHL分解について書きます。 HL分解+SegTreeでパス上のクエリに答えると、最悪ケースで O(log2 N) per query ですが、これを O(logN) per query に改善したいと思います。 アイデア HL分解の詳細についての解説は省きます。たくさんネットに資料は転がっているので探してください。 HL分解+SegTreeでパス上のクエリに答えるのは 木をHL分解でパスに分解し パスをSegTreeで管理する という 2ステップからなります。パスに分解してまとめた後の木の高さが O(logN)、そのパスへのクエリが O(logN) で、合わせて計算量は O(log2 N) です。 実は 2つめのステップで、あえてアンバランス(完全二分木ではない)なSegTreeを使うことで、logを1つ落とすことができます。 1つめのステップは普通のHL分解と全く同一