扫描线算法可解决平面内平行坐标轴的线段有关的问题，例如求平面上平行于坐标轴的矩形的面积并，其原理在于模拟一条扫描线从下往上扫描。线段树是一种灵活的 Leafy Tree，可以灵活地扫描线上统计线段的分布情况，将一部分信息储存在分支节点上，另一部分信息下传至叶子节点，因此线段树是扫描线算法的核心。
算法实现
例题：Luogu P5490 【模板】扫描线
假设我们要求如图两个矩形的面积并。
我们无法直接求这样一个不规则图形的面积，于是对矩形按照平行于 \(x\) 轴的线段进行分层，就像下面这样：
现在我们将原图转化为了很多矩形。我们只需要用每个矩形的水平宽乘高就得到了矩形的面积。
问题转化为：如何求出每个矩形的水平宽？
水平宽由水平的线段堆叠形成：
很多不同位置的线段堆叠，求堆叠后的长度并，很容易想到离散化后，使用线段树维护。
这样我们可以模拟一条扫描线从底部往上扫描，每次经过一条线段就把它加入线段树中或将与它同一个矩形的线段从线段树中删除。
线段树上要记录当前段被覆盖的长度和被完全覆盖的次数。由于每个水平线段的信息对应着固定的线段树节点，而且未来有可能被清除，因此完全覆盖的标记既不需要也不能够下传，而要使用标记永久化。若当前段被完全覆盖，那么覆盖的长度就是段长，否则就是左子节点的覆盖长度和右子节点的覆盖长度之和。
上代码！
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct line {
int l, r, y, w;
bool operator < (line b) const {
return y < b.y;
}
}ln[2 * MAXN];
int n, m, a, b, c, d, xp[2 * MAXN], son[4 * MAXN][2], tag[4 * MAXN], root, cnt;
long long sum[4 * MAXN];
int build (int tl, int tr) {
int cur = ++cnt;
if (tl != tr) {
int mid = (tl + tr) >> 1;
son[cur][0] = build (tl, mid);
son[cur][1] = build (mid + 1, tr);
}
return cur;
}
void pushup (int cur, int tl, int tr) {
if (tag[cur]) sum[cur] = xp[tr + 1] - xp[tl];
else sum[cur] = sum[son[cur][0]] + sum[son[cur][1]];
}
void modify (int cur, int tl, int tr, int ml, int mr, int x) {
if (ml <= tl && tr <= mr) {
tag[cur] += x;
pushup (cur, tl, tr);
}
else {
int mid = (tl + tr) >> 1;
if (ml <= mid) modify (son[cur][0], tl, mid, ml, mr, x);
if (mr > mid) modify (son[cur][1], mid + 1, tr, ml, mr, x);
pushup (cur, tl, tr);
}
}
int main () {
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> a >> b >> c >> d;
if (a > c) swap(a, c);
if (b > d) swap(b, d);
ln[2 * i - 1] = {a, c, b, 1};
ln[2 * i] = {a, c, d, -1};
xp[2 * i - 1] = a;
xp[2 * i] = c;
}
sort (xp + 1, xp + 2 * n + 1);
m = unique (xp + 1, xp + 2 * n + 1) - xp - 1;
for (int i = 1;i <= 2 * n;i++) {
ln[i].l = lower_bound (xp + 1, xp + m + 1, ln[i].l) - xp;
ln[i].r = lower_bound (xp + 1, xp + m + 1, ln[i].r) - xp;
}
root = build (1, m - 1);
sort (ln + 1, ln + 2 * n + 1);
long long ans = 0;
for (int i = 1;i < 2 * n;i++) {
modify (root, 1, m - 1, ln[i].l, ln[i].r - 1, ln[i].w);
ans += 1LL * (ln[i + 1].y - ln[i].y) * sum[root];
}
cout << ans << endl;
return 0;
}
易错点
主要是在实现线段树时，注意搞清楚什么标记该下传，什么标记不该。
拓展
扫描线的精髓在于使用线段树维护线段的长度，但其实线段树还可以干很多事，比如这道题：
例题：Luogu P8734 [蓝桥杯 2020 国 A] 奇偶覆盖
这道题将维护面积改为了分别维护奇覆盖和偶覆盖的面积。我们只需要在线段树上做修改：维护每个节点被完全覆盖的次数，奇数次覆盖的面积，和偶数次覆盖的面积。注意在 pushup 时，若该节点被完全覆盖过，我们需要优先将子结点中奇数覆盖的长度上传，若该节点被完全覆盖了偶数次，则子节点奇数覆盖的长度等于当前节点奇数覆盖的长度，反之则等于当前节点偶数节点覆盖的长度，然后当前节点的另一个长度只需要使用节点表示的段长减去已求得的长度即可求出。若没有被完全覆盖过，则直接将子节点的数据上传即可。
上代码！ (gugu)
通过此题，我们发现扫描线的精髓在于线段树作为一个 Leafy Tree 维护线段信息的灵活性。
总结
扫描线这个算法能解决的问题是相对单一的，但扫描线能教给我们的其实主要是线段树作为 Leafy Tree 将一部分标记储存在结构节点而不下传的操作，以及通过离散化将直线上的点表示在线段树上并进行区间操作的方式。同时，扫描线本身也是一个基于时间戳的离线算法，其中包含了典型的从空间中抽象出时间轴的操作，它起到了在空间上将二维降为一维的效果。
例题
Luogu P8146 [JRKSJ R4] risrqnis
Luogu P1856 [IOI1998] [USACO5.5] 矩形周长Picture