找到间隔中具有最小绝对差异的两个元素

Question

我给出了一个数组和LR类型的查询列表,这意味着找到任意两个数组元素之间的最小绝对差值,使得它们的索引在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]],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是树的根.