log(n) で次の 3 つのクエリを実行できるデータ構造が必要です。n は数値の範囲です。
- insert(a,b) : 間隔 [a,b] を挿入します。
- count(x) : ポイント x を含む間隔の数をカウントします。
- remove(a,b) : 間隔のセットから間隔 [a,b] を削除します。
インターバル ツリーに出くわしましたが、C++ での実装には Red Black Trees を使用する必要があります。ツリーをゼロから作成することを避けようとしていますが、C++ stl のように実装したり、これらの操作を実行し<map>たりする方法はありますか?<set>
編集 必要なのはポイントを含む間隔のカウントだけなので、バイナリ インデックス ツリーを使用しました。その実装は簡単で、上記のクエリを O(log(n)) 時間で実行します。