成对向量搜索

除了前面的答案外,这里还有一个如何准备范围以优化后续查找的建议。这个想法归根结底是对所有显著不同的输入值预先计算结果,但是在值没有显著差异的情况下要聪明。

为了说明我的意思,让我们考虑一下这个范围序列:

1, 3
1, 8
2, 4
2, 6

准备好的输出结构如下:

1, 2 -> 2
2, 3 -> 4
3, 4 -> 3
4, 6 -> 2
6, 8 -> 1

对于范围内的任何数字 1, 2 ,初始序列中有两个匹配范围。对于范围内的任何数字 2, 3 ,有四个匹配项等。请注意,现在这里有五个范围,因为有些输入范围部分重叠。因为这里的每个范围的结束值也是下一个范围的开始值,所以可以优化结束值。结果看起来像一张简单的地图:

1 -> 2
2 -> 4
3 -> 3
4 -> 2
6 -> 1
8 -> 0

请注意,最后一个范围没有一个后续范围,因此显式零成为必需的。对于第一个值之前的值,这是隐含的。要查找值的结果,只需查找小于或等于该值的键。这是一个简单的O(log n)查找。

首先,如果您只是对这些对进行了一次简单的扫描,您将拥有O(N)复杂性!O(n log n)来自排序,对于一次性操作,这只是开销。这甚至可能是最好的方法,如果不重用结果,即使只执行一些查询,也可能比排序更好。确保您允许自己关闭算法。

无论如何,让我们考虑一下您需要进行许多查询。然后,改进事情的一个相对明显的步骤是在排序之后不要一步一步地重复。相反,您可以对下限进行二进制搜索。简单地把序列分成两半。下限可以在任意一半中找到,您可以通过查看分区之间的中间元素来确定。重复,直到找到第一个不可能包含搜索值的元素,因为它的起始值已经较大。

关于另一个方向,事情并不那么容易。仅仅因为按起始值对范围进行了排序,并不意味着也对结束值进行了排序。同样,匹配的范围和不匹配的范围可以在序列中混合,所以这里您必须执行线性扫描。

最后,一些注意事项:

• 您可以使用多线程并行此算法。
• 根据您在外循环中搜索的次数m,您还可以将外循环与内循环切换。这意味着,对于每对输入向量,都要检查m搜索值是否在范围内。这可能更好,特别是当m搜索适合CPU缓存时。

对于段树、二叉索引树、间隔树来说,这是一个非常典型的样式问题。

您必须对数组执行两个操作 arr .

在一个数组上有两个操作 ARR :
1。 范围更新 : Add(a, b): for(int i = a; i <= b; ++i) arr[i]++
2。 点查询 : Query(x): return arr[x]

或者,你可以稍微巧妙地阐述你的问题。
1。 点更新 : Add(a, b): arr[a]++; arr[b+1]--;
2。 范围查询 : Query(x): return sum(arr[0], arr[1] ..... arr[x]);

在上面的每种情况下,您都有一个O(N)操作和一个O(1)操作。

对于第二种情况,查询本质上是前缀和计算。二叉索引树在这项任务中特别有效。

Tutorial for Binary Indexed Trees

重要思想:阵列压缩

你提到过矢量大小 10^6 ,所以可能无法创建这么大的数组。如果您能够创建一个由 a S和 b S和 x 先把它们翻译成数字 1 到 size of set .

超级聪明的想法:莫氏算法

只有允许您脱机解决问题时才允许这样做。这意味着可以获取所有查询点 X 作为输入,按照您喜欢的任何顺序解决它们并存储解决方案,然后按正确的顺序打印解决方案。

如果这是你的情况,请说明,只有这样我才能进一步阐述。但是二叉索引树将比mo的算法更有效。

编辑:

因为间隔值的类型是 double ,在使用我的解决方案之前,必须将它们转换为整数。我举个例子,

Intervals = (1.1 to 1.9), (1.4 to 2.1) Query Points = 1.5, 2.0

这里所有感兴趣的点并不是所有可能的加倍,而是上面的数字。 = {1.1, 1.4, 1.5, 1.9, 2.0, 2.1}

如果我们把它们映射成正整数:

1.1 --> 1
1.4 --> 2
1.5 --> 3
1.9 --> 4
2.0 --> 5
2.1 --> 6

然后可以使用段树/二元索引树。

对于每对a,b可以分解,使a=+1和b=-1表示对特定值有效的范围数。然后in变成一个简单的o(log n)查找,以查看包含搜索值的范围有多少。