使用线段树的矩形并集面积
Area of Union Of Rectangles using Segment Trees
我正在尝试了解可用于计算一组轴对齐矩形的并集面积的算法。
我遵循的解决方案是：http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/
我不明白的部分是：
The segment tree is the right choice for this data structure. It has complexity O(logn)
for the update operations and O(1)
for the query. We need to augment the segment tree with a score per node, with the following properties.
- every node corresponds to a y-interval being the union of the elementary y-intervals over all the indices in the span of the node.
- if the node value is zero, the score is the sum of the scores of the descendants (or 0 if the node is a leaf).
- if the node value is positive, the score is the length of the y-interval corresponding to the node.
我们如何在 O(n log n) 中实现这一目标？
我的想法是创建一个线段树，并在扫线时遇到范围（y 范围为矩形的高度）时更新每个范围的值。然后对于每个区间（排序后的 x 数组中的两个连续元素，通过查看线段树中所有元素的总和，将 Δx 乘以该区间中活跃的 y 范围的总长度）
这仍然会导致我们在线段树的基础中有 max(y) - min(y) 个元素。
因此，我不确定这是 O(n log n) - 其中 n 是矩形的数量。
如有任何帮助，将不胜感激。
谢谢！
让我们考虑一些简单的情况：
根据您的理解，您将在基础上创建具有 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个这样的坐标
因此我们可以将所有坐标映射到一些整数，以便它们更适合线段树。
这被称为坐标压缩，可以通过以下方式完成：
- 将所有 y 坐标存储在数组中
- 排序数组并删除重复项
- 使用 map 或 hashMap 将原始坐标映射到它在排序数组中的位置
因此在我们的示例中它将是：
[1,3,6,11] - 没有要删除的重复项，所以数组仍然
[1,3,6,11]
mp[1]=1, mp[3]=2, mp[6]=3, mp[11]=4
所以现在算法保持不变，但我们可以使用其基础中最多只有 2*n 个节点的线段树。
我们还需要稍微修改一下线段树，
我们现在将保留 y 坐标的间隔是 on/off
，而不是保持打开或关闭的 y 坐标
所以我们将有间隔 [y0,y1],[y1,y2], ... 的所有唯一排序值的节点。
此外，所有节点都将为总和贡献 y[i]-y[i-1]（如果它们在范围内且处于活动状态）而不是一个。
所以我们的新线段树应该是这样的：
How do we achieve this in 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] 子树下的所有单个段节点。
因此，searching/updating 过程如下所示。
- 如果一个父节点[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）。
我正在尝试了解可用于计算一组轴对齐矩形的并集面积的算法。
我遵循的解决方案是：http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/
我不明白的部分是：
The segment tree is the right choice for this data structure. It has complexity O(logn) for the update operations and O(1) for the query. We need to augment the segment tree with a score per node, with the following properties.
- every node corresponds to a y-interval being the union of the elementary y-intervals over all the indices in the span of the node.
- if the node value is zero, the score is the sum of the scores of the descendants (or 0 if the node is a leaf).
- if the node value is positive, the score is the length of the y-interval corresponding to the node.
我们如何在 O(n log n) 中实现这一目标？
我的想法是创建一个线段树，并在扫线时遇到范围（y 范围为矩形的高度）时更新每个范围的值。然后对于每个区间（排序后的 x 数组中的两个连续元素，通过查看线段树中所有元素的总和，将 Δx 乘以该区间中活跃的 y 范围的总长度）
这仍然会导致我们在线段树的基础中有 max(y) - min(y) 个元素。
因此，我不确定这是 O(n log n) - 其中 n 是矩形的数量。
如有任何帮助，将不胜感激。
谢谢！
让我们考虑一些简单的情况：
根据您的理解，您将在基础上创建具有 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个这样的坐标
因此我们可以将所有坐标映射到一些整数，以便它们更适合线段树。
这被称为坐标压缩，可以通过以下方式完成：
- 将所有 y 坐标存储在数组中
- 排序数组并删除重复项
- 使用 map 或 hashMap 将原始坐标映射到它在排序数组中的位置
因此在我们的示例中它将是：
[1,3,6,11]- 没有要删除的重复项，所以数组仍然
[1,3,6,11] mp[1]=1, mp[3]=2, mp[6]=3, mp[11]=4
所以现在算法保持不变，但我们可以使用其基础中最多只有 2*n 个节点的线段树。
我们还需要稍微修改一下线段树， 我们现在将保留 y 坐标的间隔是 on/off
，而不是保持打开或关闭的 y 坐标所以我们将有间隔 [y0,y1],[y1,y2], ... 的所有唯一排序值的节点。
此外，所有节点都将为总和贡献 y[i]-y[i-1]（如果它们在范围内且处于活动状态）而不是一个。
所以我们的新线段树应该是这样的：
How do we achieve this in 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] 子树下的所有单个段节点。
因此，searching/updating 过程如下所示。
- 如果一个父节点[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）。