[data-structure] Decremental Set

[ei1333]

[data-structure] Decremental Set

file name

src/data-structure/decremental-set.hpp

TODO

• [ ] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [ ] verify

note

• 16 を $O(N + Q)$ にするために必要

• 名前は Decremental Set で良いか？

- A = {1, 2, ..., n} で初期化
- A ← A \ {i} を O(1)
- min { x ∈ A | x > i } を O(1)
ならギリ需要ありそう

— 寝る (@noshi91) May 2, 2021

[ei1333]

static LCA 実装軽いかなと思ったらあんまり軽くはならなくてヘラヘラしていたんだけど、こっから更に実装重くして α(N) 落とす理由あるか？

[ei1333]

このライブラリに線形RMQをふくめるかとかにもよりそう

[ei1333]

SAISはあってもよさそうだけど