范围查询半群运算符（union）

Question

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

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

我查了维基百科的范围查询，它暗示姚（82年）显示了一个算法，运算符（联合似乎是）具有线性预处理时间和空间以及几乎不变的查询时间。不幸的是，这篇文章无法自由获得。

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

Answer 1

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

Answer 2

您可以通过执行二次时预计算回答您的任何疑问的固定时间：

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由一个散列表支持），并且有一个二次数的间隔。

如果您没有关于查询的更多信息（查询总数，间隔分布），则基本上无法做得更好，因为间隔总数已经是二次方。接收的形式A [i..j]，预先计算的查询（在O(n)时间）对于所有的间隔A[i..k]答案后，k>=i：

可以通过n线性上即时计算折衷二次预计算。这将保证分期偿还的复杂性将保持二次方，并且您不会被迫在开始时执行完整的二次预计算。

请注意，由于您完全扫描了每个区间，所以显而易见的算法（在语句中称为明显的算法）是立方体。

Answer 3

下面是另一种可能与分段树有密切关系的方法。将数组元素看作完整二叉树的叶子。如果数组中有2^n个元素，则该整棵树有n个级别。树存储的每个内部节点上存在叶子下方的点的联合。数组中的每个数字需要在每个级别出现一次（如果有重复，则数量较少）。所以空间成本是log n的一个因素。

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

所以回答查询所需半群操作次数为O（log n）的 - 但请注意，半群操作可能是昂贵的，因为你可能会形成两个大集合的并集。