永続Queue
永続Queueについての記事があまり見当たらなかったのでメモ
永続Queue is 何
Persistent Queue
↑こんな感じの操作が出来るデータ構造です
昔のデータへのaccessがO(1)とかO(logN)で済みます(適当)
解くだけならクエリから木を構築してEuler Tourしてもできますが、今回はオンラインで解くことを目指します
各操作
永続Queue自体は一番前と後ろのポインターのみを持ちます
突然ですが皆さんはダブリングを知っていますか？ 僕は知っています
ダブリングというのは各Nodeに1,2,4,...2^kつ前のポインターを前処理して、Node間の移動をO(logN)で行う手法です
例えば5つ前のNodeを参照したいとき、4つ前に戻ってから1つ前を参照すればよいです
よって、各Nodeには値とindex、そして1,2,4,...,2^kつ前のポインターを持ちます
push(x):一番後ろにxを追加した後のqueueを出力
新しいNodeを作って子のポインターを前処理するだけです かんたん
pop(x):一番前のNodeを削除した後のqueueを出力
一番後ろから(size-1)つ前のポインターを参照してそれを一番前に変更すればよいです
__builtin_clz()とかを使えば楽に実装できます
