使用段树的矩形并集区域

Question

我正在尝试了解可用于计算一组轴对齐矩形的并集面积的算法。

我正在关注的解决方案在这里：http : //tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

我不明白的部分是：

段树是此数据结构的正确选择。更新操作的复杂度为O（logn），查询的复杂度为O（1）。我们需要为每个节点添加一个分数，并具有以下属性。

• 每个节点对应一个y间隔，该y间隔是该节点范围内所有索引上基本y间隔的并集。
• 如果节点值为零，则分数是后代分数的总和（如果节点是叶，则分数为0）。
• 如果节点值为正，则分数为与该节点相对应的y间隔的长度。

我们如何在O（n log n）中实现呢？

我的想法是创建一个线段树，并在扫线时遇到范围（y范围为矩形的高度）时更新每个范围的值。然后，对于每个间隔（在已排序的x数组中，两个连续的元素，通过查看段树中所有元素的总和，将x乘以该间隔中有效y范围的总长度）

这仍然会使我们在细分树的基础中具有max（y）-min（y）元素。

因此，我不确定这是O（n log n）-其中n是矩形的数量。

非常感谢您的帮助。

谢谢！

Answer 1

让我们考虑一些简单的情况：

根据您的理解，您将创建底部有 11 - 1 = 10 个节点的线段树，如下所示：

请注意，base 中只有 9 个节点，因为第一个节点用于区间 [1,2]，下一个节点用于区间 [2,3]，依此类推

当您输入某个矩形时，您将根据其 y 坐标更新其范围，因此在 x=0 上遇到第一个矩形后，您的线段树将如下所示：

我们还需要使用称为惰性传播的东西来更新树上的活动间隔，因此所有活动间隔都会为总和贡献 1。

因此，当前方法的复杂性类似于 O(K log K)，其中 K = max(y)-min(y)

我们可以轻松地将其减少到 O(n log n)，其中 n 是矩形的数量。

请注意，只有重要的 y 坐标是存在的，因此在本例中为 1,3,6,11

另请注意，最多有 2*n 个这样的坐标

因此，我们可以将所有坐标映射到一些整数，以便它们更好地适合线段树。

这称为坐标压缩，可以通过以下方式完成：

1. 将所有 y 坐标存储在数组中
2. 对数组进行排序并删除重复项
3. 使用map或hashMap将原始坐标映射到它在排序数组中的位置

所以在我们的例子中它将是：

1. [1,3,6,11]
2. 没有重复项要删除，所以数组仍然[1,3,6,11]
3. mp[1]=1, mp[3]=2, mp[6]=3, mp[11]=4

所以现在算法保持不变，但我们可以使用线段树，其基数最多只有 2*n 个节点。

另外，我们需要稍微修改我们的线段树，而不是保留哪些 y 坐标打开或关闭，我们现在将保留 y 坐标的哪些间隔打开/关闭

因此，对于 y 的所有唯一排序值，我们将有区间 [y0,y1],[y1,y2], ... 的节点。

此外，所有节点都会将 y[i]-y[i-1] 贡献给总和（如果它们在范围内并且处于活动状态），而不是 1。

所以我们的新线段树将是这样的：