スキップリストで区間を管理するやつ

はじめに

　スキップリストで区間の管理をする方法が載ってそうな記事があまりなかったので書きました(雑記事です)

できること

スキップリストは

• insert

• erase

• access

• lower_bound

• split

• concatenate

• 区間和

• 区間更新

とかができます。あと永続化もできるっぽいんですが僕はやってません・・・

スキップリスト自体の概要

　Wikipediaに載ってます

ランダムアクセスの方法

　Wikipediaに載ってます

区間管理の方法

　下のようなスキップリストに区間minの情報を持たせる事を考えます。

スキップリストの例

　このリストからノード部分だけを切り出すとこんな感じにかけて、

ノード部分を切り出したやつ

　空いてる部分を横に伸ばすとこんな感じになります。

区間を持たせたやつ

　各ノードごとに下の段の値の最小値を持たせると、こうなります。

区間minを持たせたやつ

　こうするとなんかセグメント木っぽく見えて、実際セグ木っぽい感じで下図のように区間取得ができます。

区間]を取得する例

　もう書く事がないのでこの話はここでおわりです・・・

実装

　実装を、しました・・・

・提出コード(一点更新+区間min)

・提出コード(一点更新+一次関数の合成)

・提出コード(区間加算+区間min)

・ライブラリ(区間和)

・ライブラリ(区間加算)

なぜ広まってないの？？？？？？

・見た目に対して実装がダルい

・遅延伝播とかいろいろやるとかなりバグりやすい

・スキップリストに興味持つ人間のうち95割はすでに平衡二分木を持ってそう

・そもそも色々できる事が知られていない

　とかが理由なんじゃない？(適当)

おわり

　区間加算ができる事に気づいた時は絶対流行ると思ったんだけど、予想より実装が楽じゃなかったので微妙な気持ちになった・・・