查找范围内的最接近数字

Question

我想到了一个问题如下:

我们有一个大小为n的整数数组A,我们有测试用例t,在每个测试用例中我们给出一个数字m和一个范围[s,e],即我们给出s和e,我们必须找到最接近的该数组范围内的m数(A [s] -A [e]).

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

例如:

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

所以答案应该是18.

约束:

n<=10^5
t<=n

我能想到的只是针对每个测试用例的O(n)解决方案,我认为存在更好的解决方案.

Answer 1

这是一个草图:从数据中创建一个分段树.在每个节点上,除了左右索引等常用数据外,还可以存储以该节点为根的子树中找到的数字,以排序顺序存储.当您以自下而上的顺序构造分段树时,可以实现此目的.在叶子正上方的节点中,您按排序顺序存储两个叶子值.在中间节点中,您将数字保留在左子项和右子项中,您可以使用标准合并将它们合并在一起.树中有O(n)个节点,保留这些数据应该采用整体O(nlog(n)).

获得此树后,对于每个查询,沿着路径走,直到到达给定范围内的相应节点([s,e]).如教程所示,一个或多个不同的节点将组合在一起形成给定的范围.由于树深度为O(log(n)),即每个查询到达这些节点的时间.每个查询应为O(log(n)).对于完全位于范围内的所有节点,在存储在这些节点中的排序数组中使用二分搜索找到最接近的数字.再次,O(log(n)).找到所有这些中最接近的,这就是答案.因此,您可以在O(log(n))时间内回答每个查询.

我链接到的教程包含其他数据结构,例如稀疏表,它们更容易实现,并且每个查询应该给出O(sqrt(n)).但我对此并没有多想.