あなたの庭に永続データ構造を飾りませんか？ - noshi91のメモ2019/02/06 永続 Stack のやや丁寧な実装例を追加しました 2020/12/13 数式などを整えました 概要 あなたのライブラリに新しい彩りを与える永続データ構造の紹介です。 永続データ構造とは 永続データ構造とは、普段のデータ構造で更新をするときに更新前の状態のデータも保存しておけるデータ構造です。 唐突ですが、数列 に対するクエリを処理する問題を考えてみてください。 : に を加える : " 番目のクエリ直後の" の和を出力 のクエリを一緒にソートすればいつもの Segment Tree で解くことが出来ます。 ではこれがオンラインクエリだったらどうでしょうか。 これは Segment Tree では容易には解くことが出来ません。 こういった「過去の状態が必要になる」状況で永続データ構造は効率的です。 永続 Stack 具体的に、基本的なデータ構造である Stack の永
