是否有一个数据结构表示一个大的（64位）整数集S，它以空开始并支持以下两个操作：insert(s)将数字s插入到S中；minmod(m)返回s中的数字S，使s 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操作迭代它们；然后insert isminmod和minmod isO(1)，这将花费O(|S|)时间进行O(n^2)操作（例如，nn/2操作之后的insertn/2操作将大约花费minmod操作）。
那么：对于一系列的n^2/4操作，有没有可能比O(n^2)做得更好呢？可能n或O(n sqrt(n))？如果这是可能的，那么我还想知道是否有数据结构允许从O(n log(n))中删除单个元素，或者在一个间隔内删除所有数字。
最佳答案
另一种基于平衡二叉搜索树的思想，如Keith的答案。
假设到目前为止所有插入的元素都存储在平衡的bst中，我们需要计算minmod(m)。把我们的集合S看作一个数子集的并集，位于区间[0，m-1]、[m，2m-1]、[2m，3m-1]……答案显然是我们在每一个区间内的最小值。因此，我们可以通过查找树来找到最小的间隔数。这很容易做到，例如，如果我们需要在[a，b]中找到最小值，如果当前值大于a，我们将向左移动；否则，我们将向右移动，跟踪到目前为止遇到的[a，b]中的最小值。
如果我们假设m在[1，2^64]中均匀分布，那么我们来计算我们需要的查询数的数学期望。
对于[2^63，2^64-1]中的所有m，我们需要两个查询。概率是1/2。
对于[2^62，2^63-1]中的所有m，我们需要4个查询。概率是1/4。
…
对于[1,64]中的k，数学期望为sum[1/（2^k）*2^k]，这是64个查询。
因此，综上所述，平均minmod(m)查询复杂度为O（64×Logn）。一般来说，如果我们m有未知的上界，这将是o（logmlogn）。BST更新是已知的O（Logn），因此在N个查询的情况下的总体复杂度将是O（nLogm *Logn）。