algorithm - 半群运算符(联合)的范围查询

Question

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

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

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

编辑:这个问题似乎可以在 http://www.spoj.com/problems/DQUERY/ 找到

Answer 1

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