PythonでC++のMultisetっぽいことをする(2本のSegment Treeを用いた実装) - Qiita

はじめに PythonでC++のMultiset（多重集合）っぽいデータ構造を実装するシリーズ第2弾です。 前回のheapqを用いた実装では多重集合で ・値の挿入 ・最大値の取り出し ・最小値の取り出し ・ある値xが含まれているか といったクエリをそれぞれO(logN)で処理できるものを実装しました。(Nは多重集合のサイズ) この記事ではこれらのクエリに加え二分探索のようなことが行えるもの、つまり ・ある値x未満で最も大きい数は何か？ ・ある値x以上で最も小さい数は何か？ というクエリにもO(logN)で答えられるようなデータ構造を2本のSegment Treeを用いて実装していきたいと思います。 背景 実は先日のABC217のD問題でこの二分探索を行えるデータ構造を必要とする問題が出題され話題になりました。 C++で参加していた人からすると標準ライブラリのsetを使うだけで実装が楽だった