algorithm - 找出区间内绝对差值最小的两个元素

Question

我得到了一个数组和一个 L R 类型的查询列表，这意味着找到任何两个数组元素之间的最小绝对差，使得它们的索引在 L 和 R 之间(包括在内)(这里数组的起始索引改为 1在 0)

例如，使用元素为 2 1 8 5 11 的数组 a 那么查询 1-3 将是 (2 1 8) 答案将是 1=2-1，或者查询 2-4 (1 8 5 ) 答案是 3=8-5

现在这很容易，如果您必须查看一个区间，您可以对该区间进行排序，然后将第 i 个元素与第 i+1 个元素进行比较，并存储每个 i 的最小差值。

问题是我将有很多时间间隔来检查我必须保持原始数组完好无损。

我所做的是构建一个新数组 b，其中包含第一个数组的索引，使得 a[b[i]] <= a[b[j]] for i <= j。现在对于每个查询，我循环遍历整个数组并查看 b[j] 是否在 L 和 R 之间，如果它比较它的绝对差异与第一个下一个元素，它也在 L 和 R 之间保持最小值，然后做同样的事情那个元素，直到你到达终点。

这是低效的，因为对于每个查询，我都必须检查数组的所有元素，尤其是当查询与数组的大小相比较小时。我正在寻找一种节省时间的方法。

编辑: 数字不必是连续的，也许我举了一个错误的数组作为例子，我的意思是例如如果它是 1 5 2 那么最小的差异是 1 =2-1。在排序数组中，最小的差异保证在两个连续元素之间，这就是为什么我想到排序

Answer 1

我将草拟一个 O(n (√n) log n) 时间的解决方案，它可能足够快？当我放弃体育节目时，计算机速度要慢得多。

高级思想是通过以下操作将 Mo 的技巧应用于数据结构。

insert(x) - inserts x into the underlying multiset
delete(x) - deletes one copy of x from the underlying multiset
min-abs-diff() - returns the minimum absolute difference
                 between two elements of the multiset
                 (0 if some element has multiplicity >1)

读入所有查询区间[l, r]，按字典序非递减排序(floor(l/sqrt(n)), r)其中n是输入的长度，然后处理一个区间I，插入I - I'中的元素，其中 I'为上一个区间，删除I'-I中的元素，报最小绝对差。 (有趣的排序顺序的要点是将操作数从 O(n^2) 减少到 O(n √n) 假设 n查询。)

有几种方法可以实现具有 O(log n) 时间操作的数据结构。为清楚起见，我将使用二叉搜索树，但您也可以对数组进行排序并使用线段树(如果您没有允许您指定装饰的 BST 实现，工作量会减少)。

为每个BST节点添加三个字段:min(以该节点为根的子树中的最小值)、max(以该节点为根的子树中的最大值) , min-abs-diff(以该节点为根的子树中值之间的最小绝对差值)。这些字段可以像这样自下而上地计算。

if node v has left child u and right child w:
    v.min = u.min
    v.max = w.max
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max,
                         w.min - v.value, w.min-abs-diff)

if node v has left child u and no right child:
    v.min = u.min
    v.max = v.value
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max)

if node v has no left child and right child w:
    v.min = v.value
    v.max = w.max
    v.min-abs-diff = min(w.min - v.value, w.min-abs-diff)

if node v has no left child and no right child:
    v.min = v.value
    v.max = v.value
    v.min-abs-diff = ∞

这个逻辑可以非常紧凑地实现。

if v has a left child u:
    v.min = u.min
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max)
else:
    v.min = v.value
    v.min-abs-diff = ∞
if v has a right child w:
    v.max = w.max
    v.min-abs-diff = min(v.min-abs-diff, w.min - v.value, w.min-abs-diff)
else:
    v.max = v.value

insert 和 delete 像往常一样工作，除了装饰需要沿着遍历路径更新。对于合理的容器选择，总时间仍然是 O(log n)。

min-abs-diff 是通过返回 root.min-abs-diff 实现的，其中 root 是树的根。