algorithm - 是否有可能在分摊的次线性时间内计算一组数字的最小值模给定数字？

Question

是否有一个数据结构表示一个大集合S(64 位)整数，它开始时为空并支持以下两个操作:

• insert(s) 将数字s插入S；
• minmod(m) 返回 S 中的数 s 使得 s mod m 最小。

一个例子:

    insert(11)
    insert(15)
    minmod(7) -> the answer is 15 (which mod 7 = 1)
    insert(14)
    minmod(7) -> the answer is 14 (which mod 7 = 0)
    minmod(10) -> the answer is 11 (which mod 10 = 1)

我感兴趣的是最小化花费在一系列 n 此类操作上的最大总时间。显然可以只为 S 维护一个元素列表，并为每个 minmod 操作迭代它们；然后 insert 是 O(1) 并且 minmod 是 O(|S|)，这将花费 O(n^2) 时间 n 操作(例如，n/2 insert 操作后跟 n/2 minmod操作大约需要 n^2/4 操作)。

那么:对于 n 操作序列，是否有可能比 O(n^2) 做得更好？也许是 O(n sqrt(n)) 或 O(n log(n))？如果这是可能的，那么我也很想知道是否有数据结构额外允许从 S 中删除单个元素，或者删除一个区间内的所有数字。

Answer 1

另一个基于平衡二叉搜索树的想法，如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，我们需要 2 查询。这个概率是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).