使用线段树求矩形并的面积

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是矩形的数量。

非常感谢您的帮助。

谢谢！

- Hormigas

---

我们可以使用坐标压缩仅保留必要的坐标，因此在线段树基础中只有 O(n) 个元素。 - Photon

@Photon，你能再详细解释一下吗？或者有没有什么推荐的链接可以让我了解更多？ - Hormigas

该文本表示：“更新操作的复杂度为O(log n)，查询操作的复杂度为O(1)。”由于树最多包含n个节点，并且最多更新n次，因此最坏情况下的复杂度为O(n log n)。在实践中，复杂度为O(n log m)，其中m是树中平均节点数，可能类似于√n（因此差异不太显着，因为log√n=1/2 log n）。 - user1196549

Answer 1

让我们考虑一个简单的情况： 根据您的理解，您将创建具有11 - 1 = 10个节点的基本段树，因此类似于这样： 请注意，我们只在基本部分拥有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坐标间隔打开/关闭。

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

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

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

- Photon

---

这可能是一个天真的问题 - 但在你提供的第一张图中，每个节点的值是其子节点的最大值吗？谢谢。 - Hormigas

我不确定在我们遇到第一个矩形之后如何从第一个图形获得第二个图形。更新的y范围应该是[3,6]，对吗？ - Hormigas

感谢您的回复。我仍然不确定“请注意，我们在基础中只有9个节点，因为第一个节点是区间[1,2]，下一个节点是区间[2,3]等等。”从https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/中了解到的线段树的内容是，基本节点是单个元素。因此，对于区间[0,0]，[1,1]等。但是，您的答案帮助我理解了坐标压缩。非常感谢！如果您能澄清上述疑问，我会很高兴。如果不能，我也理解并且非常感谢您的努力。 - Hormigas

@Anant 是的，基础线段树节点是针对单一区间 [0,0]，[1,1] 之类的数组 A[]。但在这个问题中，我们只需修改它们的意义，因此 A[0] 表示区间 [1,2]，A[1] 表示区间 [2,3]，以此类推。 - Photon

这是我高效实现的代码：https://ideone.com/jPe1n5。问题参考：https://lightoj.com/problem/rectangle-union。 - Robbinb1993

Answer 2

我们如何在O(n log n)时间复杂度内实现这一点？

考虑到每个矩形，您将要在二进制线段树中更新区间[x，y]。基本上发生的情况是，

您正在：

- 在树中以x为左边界搜索（log(N)时间） - 在树中以y为右边界搜索（log(N)时间）

假设您找到了x的节点为[x，a]，并且它具有父节点[z，a]，此父节点具有兄弟节点[a，b]。显然，如果y不在[a，b]下，则覆盖[a，b]的整个跨度，因此您增加此节点而不是[a，b]子树下的所有单独的段节点。

因此，搜索/更新过程看起来像这样。

• 如果父节点[a,c]有两个子节点[a,b]，[b,c]，并且左边界x在[a,b]中，则决定是否增加节点[b,c]中的值（取决于y是否大于c）
• 如果父节点[a,c]有两个子节点[a,b]，[b,c]，并且右边界y在[b,c]中，则决定是否增加节点[a,b]中的值（取决于x是否小于a）

实质上，在深入一个节点之前，决定是否更新其兄弟节点。

您需要决定是否更新的节点数为log(N)（对于x）+ log(N)（对于y）。

- dchneric