扫描线

扫描线：假设有一条竖直的直线，从平面的最左端扫描到最右端，在扫描的过程中，直线上的一些线段会被给定的矩形覆盖。如果我们将这些覆盖的线段长度进行积分，就可以得到矩形的面积之和。

如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。

我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记：

下面的边标记为 \(1\)；
上面的边标记为 \(-1\)。

每遇到一个矩形时，我们知道了标记为 \(1\) 的边，我们就加进来这一条矩形的长，等到扫描到 \(-1\) 时，证明这一条边需要删除，那么我们就删除这条边，利用 \(1\) 和 \(-1\) 可以轻松得到这种状态。

还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 \(r+1\) 和 \(r-1\)。

注意，需要离散化。

应用

应用1：Leetcode.850

题目

850. 矩形面积 II

给你一个轴对齐的二维数组 rectangles 。对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形左下角的坐标， (xi2, yi2) 是该矩形右上角的坐标。

计算平面中所有 rectangles 所覆盖的总面积。任何被两个或多个矩形覆盖的区域应只计算一次。返回总面积。因为答案可能太大，返回 \(10^9 + 7\) 的模。

示例 1：

输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出：6
解释：如图所示，三个矩形覆盖了总面积为 6 的区域。
从(1,1)到(2,2)，绿色矩形和红色矩形重叠。
从(1,0)到(2,3)，三个矩形都重叠。

解题思路

方法一：离散化 + 扫描线

每个矩形都有一个左边界和一个右边界：

当扫描到矩形的左边界时，直线上被矩形覆盖的长度可能会增加；
当扫描到矩形的右边界时，直线上被矩形覆盖的长度可能会减少。

假设矩形 \(rectangles\) 的个数为 \(n\) ，那么，矩形的左右边界个数为 \(2n\)，因此，扫描线在水平移动过程中，被覆盖的线段长度最多变化 \(2n\) 次，此时，我们就可以将两次变化之间的部分合并起来，一起计算：即这一部分矩形的面积，等于所有被覆盖的线段长度，乘以扫描线在水平方向移动过的距离。

这里会有一个问题，我们如何维护「覆盖的线段长度」呢？

这里同样可以使用到离散化的技巧，扫描线就是一种离散化的技巧，将大范围的连续的坐标转化成 \(2n\) 个离散的坐标。

由于矩形的上下边界也是 \(2n\) 个，它们会将 \(y\) 轴分成 \(2n+1\) 个部分，中间的 \(2n−1\) 个部分均为线段，会被矩形覆盖到，最外侧的 \(2\) 个部分为射线，不会被矩形覆盖到，并且每一个线段要么完全被覆盖，要么完全不被覆盖。

因此我们可以使用一个长度为 \(2n−1\) 的数组 \(coverTimes[i]\)，来表示扫描线上第 \(i\) 个线段被矩形覆盖的次数，即：

当扫描线遇到一个左边界时，我们就将左边界覆盖到的所有线段对应的覆盖次数 \(coverTimes[i]\) 全部加 \(1\)；
当扫描线遇到一个右边界时，我们就将右边界覆盖到的所有线段对应的覆盖次数 \(coverTimes[i]\) 全部减 \(1\)。

在处理掉一批横坐标相同的左右边界后，\(coverTimes[i]\) 如果大于 \(0\)，说明它被覆盖，我们累加所有被覆盖的线段长度，即可得到「覆盖的线段长度」。

这里，我们使用列表 \(verticalBound\) 保存所有矩形的上下边界，并对其去重，按照从小到大的顺序排序。注意，由于我们对矩形的上下边界排序了，所以，我们需要引入一个变量 \(coverFlag\) 来记录矩形上下边界覆盖的范围。

同时，使用列表 \(sweep\) 记录所有矩形的矩形的左右边界信息：\((x, i, coverFlag)\)，其中，\(x\) 为该矩形边界的横坐标，\(i\) 为该矩形的索引，\(coverFlag\) 为覆盖标记。

对于 \(coverFlag\)：

因为扫描线遇到一个矩形的左边界时，扫描线经过的区域会被该矩形覆盖，因此，记录 \(coverFlag = 1\)；
因为扫描线遇到一个矩形的右边界时，扫描线经过的区域不会被该矩形覆盖，因此，记录 \(coverFlag = -1\)；

然后，我们对所有 \(sweep\) 记录的左右边界信息，按照横坐标从小到大的顺序排序。

因此，算法的步骤如下：

首先，我们按照横坐标从小到大的顺序，遍历所有矩形的左右边界 \(sweep[i]\) ，并跳过所有横坐标相同的左右边界，并记录最后一个相同的左右边界的序号 \(j\)。
对于这 \(j - i\) 个具有相同横坐标的左右边界 \(sweep[k]\)：
- 对于任意一个左右边界 \(sweep[k]\)，可以得到：其索引为 \(i =sweep[k][1]\)，覆盖标记为 \(flag=sweep[k][2]\)；
  
  因此，其纵坐标为：\((y1, y2) = (rectangles[i][1], rectangles[i][3])\)。
- 然后，我们需要遍历扫描线上被所有上下边界覆盖的线段；
  
  对于每一条线段 \(L\)：\([verticalBound[p], verticalBound[p + 1]](0 \le p \le 2n - 1)\)，如果它落在 \([y1, y2]\) 范围内，就更新它的覆盖次数 \(coverTimes[p]\)。
然后，我们需要遍历扫描线上所有被矩形覆盖的线段，并累加覆盖区域的线段长度；

我们可以通过 \(coverTimes[p] \gt 0\)，判断当前线段是否被矩形覆盖。
最后，我们就可以通过通过被覆盖的线段长度和水平扫描过的距离，求出当前的积分区域的面积，并累加该面积的区域

起始扫描的位置为：\(x_0 = sweep[i][0]\)；

水平扫描到的最远距离就是 \(sweep[j + 1]\) 对应的位置，即 \(x_1 = sweep[j + 1][0]\)；

因此，当前积分区域的面积：\(S_i = coveredLength \times (x_1 - x_0) = coveredLength \times (sweep[j + 1][0] - sweep[i][0])\)。

方法二：线段树

方法一中对于数组 \(coverTimes\) 的所有操作，都可以使用线段树进行维护。线段树中需要存储：

该节点对应的区间被完整覆盖的次数；
该节点对应的区间被覆盖的线段长度。

线段树需要支持：

区间增加 1；
区间减少 1，并且保证每个被增加 1 的区间在之后一定会减少 1；
对于所有非 0 的位置，根据它们的权值进行求和。

由于这种方法严重超纲，因此不在这里详细阐述。

代码实现

【方法一】

from typing import List

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        # Y轴要扫描的范围
        vertical_bound = set()
        for rectangle in rectangles:
            # 下边界
            vertical_bound.add(rectangle[1])
            # 上边界
            vertical_bound.add(rectangle[3])
        vertical_bound = sorted(vertical_bound)

        m = len(vertical_bound)
        # 记录所有的左右边界
        sweep = list()
        for i, rectangle in enumerate(rectangles):
            # 左边界，遇到覆盖次数加1
            sweep.append((rectangle[0], i, 1))
            # 右边界，遇到覆盖次数减1
            sweep.append((rectangle[2], i, -1))

        # 将矩形的所有左右边界按从小到大的顺序排序
        sweep.sort()

        # cover_times[i] 表示第 i 个线段被矩形覆盖的次数
        cover_times = [0] * (m - 1)
        result = 0
        i = 0
        # 遍历所有的X轴的边界
        while i < len(sweep):
            j = i
            # 横坐标相同的左右边界
            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:
                j += 1
            if j + 1 == len(sweep):
                break

            # 一次性地处理掉[i, j]范围内，一批横坐标相同的左右边界
            for k in range(i, j + 1):
                _, index, diff = sweep[k]
                # 找到这些边界对应的纵坐标
                y1, y2 = rectangles[index][1], rectangles[index][3]
                # 遍历扫描线上所有被上下边界覆盖的线段
                for p in range(m - 1):
                    # 如果纵坐标在具有相同X边界的范围内，就更新它的覆盖次数
                    if y1 <= vertical_bound[p] and vertical_bound[p + 1] <= y2:
                        cover_times[p] += diff

            # 扫描线上被矩形覆盖的线段之和
            covered_length = 0
            # 遍历扫描线上所有被矩形覆盖的线段
            for p in range(m - 1):
                if cover_times[p] > 0:
                    # 纵坐标上每一段覆盖的范围一定是两个相邻线段的差值
                    covered_length += (vertical_bound[p + 1] - vertical_bound[p])
            # 计算扫描线经过范围内被覆盖的面积
            result += covered_length * (sweep[j + 1][0] - sweep[i][0])
            i = j + 1

        return result % (10 ** 9 + 7)

【方法二】

import bisect
from typing import List


class Segtree:
    def __init__(self):
        self.cover = 0
        self.length = 0
        self.max_length = 0

    @classmethod
    def init(cls, tree: List["Segtree"], idx: int, l: int, r: int, hbound: List[int]) -> None:
        tree[idx].cover = tree[idx].length = 0
        if l == r:
            tree[idx].max_length = hbound[l] - hbound[l - 1]
            return

        mid = (l + r) // 2
        cls.init(tree, idx * 2, l, mid, hbound)
        cls.init(tree, idx * 2 + 1, mid + 1, r, hbound)
        tree[idx].max_length = tree[idx * 2].max_length + tree[idx * 2 + 1].max_length

    @classmethod
    def update(cls, tree: List["Segtree"], index: int, l: int, r: int, ul: int, ur: int, diff: int) -> None:
        if l > ur or r < ul:
            return
        if ul <= l and r <= ur:
            tree[index].cover += diff
            cls.pushup(tree, index, l, r)
            return

        mid = (l + r) // 2
        cls.update(tree, index * 2, l, mid, ul, ur, diff)
        cls.update(tree, index * 2 + 1, mid + 1, r, ul, ur, diff)
        cls.pushup(tree, index, l, r)

    @classmethod
    def pushup(cls, tree: List["Segtree"], idx: int, l: int, r: int) -> None:
        if tree[idx].cover > 0:
            tree[idx].length = tree[idx].max_length
        elif l == r:
            tree[idx].length = 0
        else:
            tree[idx].length = tree[idx * 2].length + tree[idx * 2 + 1].length


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        hbound = set()
        for rectangle in rectangles:
            # 下边界
            hbound.add(rectangle[1])
            # 上边界
            hbound.add(rectangle[3])

        hbound = sorted(hbound)
        m = len(hbound)
        # 线段树有 m-1 个叶子节点，对应着 m-1 个会被完整覆盖的线段，需要开辟 ~4m 大小的空间
        tree = [Segtree() for _ in range(m * 4 + 1)]

        Segtree.init(tree, 1, 1, m - 1, hbound)
        sweep = list()
        for i, rectangle in enumerate(rectangles):
            # 左边界
            sweep.append((rectangle[0], i, 1))
            # 右边界
            sweep.append((rectangle[2], i, -1))
        sweep.sort()

        result = 0
        i = 0
        while i < len(sweep):
            j = i
            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:
                j += 1
            if j + 1 == len(sweep):
                break

            # 一次性地处理掉一批横坐标相同的左右边界
            for k in range(i, j + 1):
                _, index, diff = sweep[k]
                # 使用二分查找得到完整覆盖的线段的编号范围
                left = bisect.bisect_left(hbound, rectangles[index][1]) + 1
                right = bisect.bisect_left(hbound, rectangles[index][3])
                Segtree.update(tree, 1, 1, m - 1, left, right, diff)

            result += tree[1].length * (sweep[j + 1][0] - sweep[j][0])
            i = j + 1

        return result % (10 ** 9 + 7)

参考：