S空から始まり、次の 2 つの操作をサポートする (64 ビット) 整数の大きなセットを表すデータ構造はありますか?
insert(s)に数値を挿入sしSます。minmod(m)最小になるような数値sを返します。Ss mod m
例：
インサート(11)
インサート(15)
minmod(7) -> 答えは 15 (mod 7 = 1)
インサート(14)
minmod(7) -> 答えは 14 (mod 7 = 0)
minmod(10) -> 答えは 11 (mod 10 = 1)
このような一連の操作に費やされる最大合計時間を最小限に抑えることに関心がありnます。要素のリストを維持し、すべての操作Sでそれらを反復処理することは明らかに可能です。minmod次に insert isO(1)と minmod is を実行しますが、これには操作に時間O(|S|)がかかります (たとえば、操作の後に操作が続くと、大まかに操作が必要になります)。O(n^2)nn/2 insertn/2 minmodn^2/4
O(n^2)では、一連のn操作よりも優れた方法はありますか? 多分O(n sqrt(n))またはO(n log(n))？これが可能であれば、 から単一の要素を削除Sしたり、間隔内のすべての数値を削除したりすることをさらに許可するデータ構造があるかどうかも知りたいです。