配列が与えられる。前から順に走査したい。削除をしたい。
要件
- 元の配列が長さNでも、削除後が長さMならO(M)で走査できる必要がある
- ダミーの値を代入して読み飛ばす方式はNG
- 削除はO(1)でなければならない
- 要素を詰めるのはNG
- PythonのリストのremoveはNG
与えられた配列と同じサイズのゼロフィルされた配列next, prevを用意する
削除する時
prev[pos + 1 + next[pos]] += prev[pos] + 1
next[pos - 1 - prev[pos]] += next[pos] + 1
要するに双方向リンクトリスト。
単純に構築するとnext[pos] = pos + 1が初期値になるわけだが、そこからの差分だけを持つことでゼロフィルで初期化できるようにしたわけだ。
削除しかしないなら絶対アドレスを持つ必要がないからこれでよい。挿入もするなら普通の双方向リストが良い。
先頭要素は番兵。削除してはいけない。 削除するとどうなるかはまだ考察してない。
作成時のインデックスでのランダムアクセスはO(1)