在一个范围内查找最接近的数

Question

我遇到了一个与以下问题相关的情况：

我们有一个大小为n的整数数组A，我们有测试用例t，在每个测试用例中，我们都会得到一个数字m和一个范围[s,e]，即我们会得到s和e，并且我们必须在该数组的范围内（A[s]-A[e]）找到最接近m的数字。

您可以假设数组索引从1到n。

例如：

  A = {5, 12, 9, 18, 19}
  m = 13
  s = 4 and e = 5

所以答案应该是18。

限制条件：

n<=10^5
t<=n

我能想到的只有一个O(n)的解决方案，但我认为可能存在更好的解决方案。

- Akashdeep Saluja

---

如果它没有排序，那么必须访问A[s]和A[e]之间的每个值，因此它是O(n)。或者更确切地说是O(e-s)。 - femtoRgon

@femtoRgon 我知道，但是通过使用任何数据结构，我认为这是可能的（只是想一想但不确定）。 - Akashdeep Saluja

既然您指定了一个最大大小界限（10^5），那么复杂度不就是O（1） - 即常数时间吗？ - Chris

@Chris 这是对元素数量的限制，而不是它们的值。 - Ivaylo Strandjev

@izomorphius如果这些数字应该是无限精度整数，到目前为止给出的复杂度数字是错误的。 - Chris

Answer 1

这是一个简单的草图： 从数据中创建一个线段树。在每个节点上，除了通常的左右索引等数据外，还按排序顺序存储在该节点为根的子树中找到的数字。当您以自下而上的顺序构建线段树时，可以实现这一点。在叶子节点上面的节点中，您以排序顺序存储两个叶子值。在中间节点中，您保留左子节点和右子节点中的数字，然后使用标准合并将它们合并在一起。树中有O(n)个节点，并且保留这些数据应该总共需要O(nlog（n))。

一旦您拥有此树，在每个查询中，向下遍历路径直到到达给定范围（[s，e]）中的适当节点。正如教程所示，一个或多个不同的节点将组合成给定范围。由于树深度为O(log(n))，因此每个查询到达这些节点的时间为O(log(n))。对于完全位于范围内的所有节点，在其中存储的已排序数组中使用二进制搜索找到最接近的数字。同样，O(log(n))。在所有这些数字中找到最接近的数字，这就是答案。因此，您可以在O(log(n))时间内回答每个查询。

我链接的教程包含其他数据结构，例如稀疏表，这些数据结构更易于实现，并且应该每个查询给出O(sqrt(n))。但是，我没有仔细思考过这一点。

- mayank

---

你如何决定将哪些节点放入树中？您无法添加所有可能的左右索引。 - Chris

一个段树是建立在数组之上的（每个数组元素是一个叶子），每两个叶子节点合并成一个下一级节点，以此类推。您可以按照教程中给出的方式在数组上构建整棵树。然后，在任何给定范围内搜索聚合数据需要在树中向下遍历最多两个分支。 - mayank

好的，现在明白了。我错了 - 我曾经使用过线段树，但不知道如何将其应用到这个问题上。 - Chris

@mayank，我认为你的说法“最多只有两个不同的节点可以组合成给定的范围”可能是不正确的，因为范围可以通过使用超过两个节点来形成，例如当总范围为[1,8]且所需范围为[2,7]时，需要使用四个线段树节点。如果我错了，请纠正我。 - Akashdeep Saluja

@AkashdeepSaluja 是的，在仔细考虑后，你是正确的。目标节点的数量可能超过2个。但是遍历时间仍然是O(log(n))，尽管我无法严格证明它。我会编辑我的答案。 - mayank

Answer 2

我相当确定没有更快的解决方案。你问题的一个轻微变化是：

没有数组A，但每个测试用例都包含一个未排序的数字数组进行搜索。（从s到e的A的数组切片）。

在这种情况下，每个测试用例都只能使用线性搜索，显然没有更好的方法。

现在，你原始问题比上面的变化方式更具体的地方在哪里？唯一添加的信息是所有切片来自同一个数组。我不认为这个额外的约束条件可以用于算法加速。

编辑：我被纠正了。段树数据结构应该可以工作。

- Chris

---

那不是微小的变化，而是重大的差异。当你事先有了 A，你可以在预处理期间创建一个数据结构，以便进行更快速的搜索。 - interjay

我的观点是这样的数据结构不存在，但另一个答案中的线段树想法让我改变了看法。 - Chris

Answer 3

对数组进行排序并进行二分查找。复杂度：O(nlogn + logn * t)

- CSStudent

---

无法工作 - 您在查询中使用了原始数组中的索引。请再次阅读该语句。 - Ivaylo Strandjev