问第一元素之间的差小于或等于第二元素中的最小值的对的数量

EN

让我们按照第二个值以非递增的顺序对我们的对进行排序。然后按此顺序遍历这些对。假设当前对具有索引i，并查看所有对(j, i)，其中为j < i。我们知道这些对中的第二个元素的最小值是pairs[i].second (因为它的顺序不是递增的)。然后我们需要找出索引的数量j，其中

 |pairs[j].first - pairs[i].first| <= pairs[i].second

让我们重新制定:我们需要找出索引为j < i的对的第一个元素的数量，它们位于区间内：

[pairs[i].first - pairs[i].second, pairs[i].first + pairs[i].second]

例如，可以使用O(log(n))中的augmented self-balancing BST (我们可以保留和更新每个顶点中的子代数量)来实现这一点。伪码：

res = 0
sort pairs by second value in non-increasing order
for i = 1 to n
    res += number of elements in BST on interval [pairs[i].first - pairs[i].second, pairs[i].first + pairs[i].second]
    add pairs[i].first to BST   

总体复杂度将是O(n*log(n))。

如果对中的整数值为O(n)，则可以使用Fenwick tree或Segment tree替换BST。

当你把这些对看作是二维点的时候，你就可以在一个坐标系中说明这个问题。

现在，您希望将每个点对(点)与点上方具有y坐标宽度的区域中的所有点对(点)连接起来。下图中给出了两个示例。以这种方式构建区域可以确保：

1. 您认为的点的y坐标是上面所有点中的最小值。
2. 这些点的x坐标之差不大于y坐标。

​

​

现在的问题是，我们如何快速找到该区域中的点。

对于这些类型的查询，通常使用R-Trees。你可以在O(n log n)中构建一棵R-树。查询的复杂性取决于查询的选择性，在这个问题中还取决于数据分布。如果幸运的话，它是O(log )，但对于每个点，它也可能收敛到O(n)。

但是，如果我理解正确的话，您并不是对所有的配对都感兴趣，而只是对配对的数量感兴趣。如果是这种情况，您可以向R-Tree页面添加一个计数器，用于存储每个页面中存储的点数。然后，您实际上不必验证所有的点，这可以使您更接近每个点的O(log )。

你们的配对是坐标。把它们当做位置。

对于给定的坐标(x，y)，匹配的坐标形成一个从x轴发射到高度y的圆锥体，然后它变成一个以x为中心的宽度为2y+1的列，直到无限大。

因此，现在您需要一种方法来计算这样一个区域中的元素数量，而无需执行任何按元素计算的工作。

假设您有一个从(x，y)到该点上方和左侧的点的#的映射(称之为平方累积图)。然后计算列部分需要2次查找和一次减法。应该可以在O(n lg n)时间内构建这样的映射。

可以使用类似的几何累积计数来有效地计算三角形或锥形区域中的元素的计数。例如，如果我们有一个从k到# of elements的映射，使用(x-y)>=k，您可以在1次查找中计算三角形中的元素数，然后在平方累加图中查找3次，然后进行2次减法和1次加法。

有一个相反方向的对角累积图，你现在可以计算上面指定的圆锥体中元素的数量。