4

我正在寻找实现一种算法，该算法给出一个整数数组和该数组中的范围（间隔）列表，返回每个间隔中不同元素的数量。也就是说，给定数组 A 和范围 [i,j] 返回集合 {A[i],A[i+1],...,A[j]} 的大小。

显然，天真的方法（从 i 迭代到 j 并计算忽略重复项）太慢了。Range-Sum 似乎不适用，因为 AUB - B 并不总是等于 B。

我在 Wikipedia 中查找了 Range Queries，它暗示 Yao（在 82 年）展示了一种算法，该算法对半群运算符（似乎是联合）执行此操作，具有线性预处理时间和空间以及几乎恒定的查询时间。不幸的是，这篇文章不能免费获得。

编辑：看来这个确切的问题可以在http://www.spoj.com/problems/DQUERY/

4

3 回答 3

3

有一个相当简单的算法，它使用 O(N log N) 时间和空间进行预处理，每个查询使用 O(log N) 时间。首先，创建一个持久的段树来回答范围和查询（最初，它应该在所有位置都包含零）。然后遍历给定数组的所有元素并存储每个数字的最新位置。在每次迭代中，创建一个新版本的持久段树，将 1 放在每个元素的最新位置（每次迭代只能更新一个元素的位置，因此段树中只有一个位置的值发生变化，因此可以在O(log N))。要回答查询 (l, r) 您只需要在 (l, r) 段上找到迭代初始数组的 r 元素时创建的树版本的总和。希望这个算法足够快。更新。我的解释有一个小错误：在每一步，段树中最多两个位置的值可能会发生变化（因为如果它被更新，必须将 0 放在一个数字的前一个最新位置）。但是，它不会改变复杂性。

于 2013-02-04T16:33:55.493 回答
0

您可以通过执行二次时间预计算在恒定时间内回答您的任何查询：

For every i from 0 to n-1
    S <- new empty set backed by hashtable;
    C <- 0;
    For every j from i to n-1
        If A[j] does not belong to S, increment C and add A[j] to S.
        Stock C as the answer for the query associated to interval i..j.

该算法需要二次时间，因为对于每个间隔，我们执行有限数量的操作，每个操作都需要恒定时间（请注意，集合 S 由哈希表支持），并且有二次时间间隔。

如果您没有关于查询的其他信息（查询总数、间隔分布），则基本上无法做得更好，因为间隔的总数已经是二次的。

您可以通过线性动态计算来权衡二次预计算n：在接收到 A[i..j] 形式的查询后，预先计算（O(n)及时）所有区间的答案A[i..k]，k>=i. 这将保证摊销复杂度将保持二次，并且您不会被迫在开始时执行完整的二次预计算。

请注意，明显的算法（您在语句中称为明显的算法）是三次的，因为您完全扫描每个间隔。

于 2013-02-04T17:13:22.690 回答
0

这是另一种可能与段树密切相关的方法。将数组的元素视为完整二叉树的叶子。如果数组中有 2^n 个元素，则该完整树有 n 个级别。在树的每个内部节点上，存储位于其下方叶子中的点的并集。数组中的每个数字需要在每个级别中出现一次（如果有重复则更少）。所以空间成本是 log n 的一个因素。

考虑一个长度为 K 的范围 A..B。您可以通过形成与叶子和节点相关联的集合并集来计算该范围内的点的并集，选择树上尽可能高的节点，只要下面的子树这些节点完全包含在范围内。如果你沿着范围挑选尽可能大的子树你会发现子树的大小先增加然后减小，并且所需的子树的数量仅随着范围大小的对数增长 - 在开始时如果您只能采用大小为 2^k 的子树，它将在可被 2^(k+1) 整除的边界上结束，并且您将有机会获得大小至少为 2^(k+1) 的子树作为下一个如果您的范围足够大，请采取步骤。

因此，回答查询所需的半组操作数为 O(log n) - 但请注意，半组操作可能很昂贵，因为您可能正在形成两个大集合的并集。

于 2013-02-04T21:20:05.787 回答