线段树的基础在于"区间查询 + 区间修改"，但真正的威力在于它的可扩展性：扫描线、区间合并、动态开点、可持久化……本节覆盖线段树在竞赛与面试中的进阶用法。
一、扫描线：矩形面积并
Mermaid · 渲染中（下方为源码）
graph TD A[矩形] --> B[扫描线扫x] B --> C[线段树维护y覆盖] C --> D[面积并]
经典问题：平面上若干矩形，求它们的面积并。
思路：沿 x 轴扫描，每遇到一条竖直边就计算"当前覆盖的 y 轴总长度 × 到下一条边的距离"。覆盖长度用线段树维护。
// 矩形面积并（LeetCode 850 思路）
class Solution {
public int rectangleArea(int[][] rectangles) {
// 事件：(x, y1, y2, +1/-1) 表示进入/离开
List<int[]> events = new ArrayList<>();
Set<Integer> ySet = new TreeSet<>();
for (int[] r : rectangles) {
events.add(new int[]{r[0], r[1], r[3], 1});
events.add(new int[]{r[2], r[1], r[3], -1});
ySet.add(r[1]); ySet.add(r[3]);
}
events.sort((a, b) -> a[0] - b[0]);
// y 坐标离散化
List<Integer> ys = new ArrayList<>(ySet);
Map<Integer, Integer> yIdx = new HashMap<>();
for (int i = 0; i < ys.size(); i++) yIdx.put(ys.get(i), i);
int[] count = new int[4 * ys.size()]; // 覆盖次数
long[] cover = new long[4 * ys.size()]; // 覆盖长度
long area = 0;
int prevX = events.get(0)[0];
for (int[] e : events) {
area += cover[1] * (e[0] - prevX);
update(count, cover, 1, 0, ys.size() - 2,
yIdx.get(e[1]), yIdx.get(e[2]) - 1, e[3], ys);
prevX = e[0];
}
return (int) (area % 1_000_000_007);
}
void update(int[] count, long[] cover, int node, int lo, int hi,
int l, int r, int val, List<Integer> ys) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) {
count[node] += val;
} else {
int mid = (lo + hi) / 2;
update(count, cover, node * 2, lo, mid, l, r, val, ys);
update(count, cover, node * 2 + 1, mid + 1, hi, l, r, val, ys);
}
if (count[node] > 0) {
cover[node] = ys.get(hi + 1) - ys.get(lo);
} else if (lo == hi) {
cover[node] = 0;
} else {
cover[node] = cover[node * 2] + cover[node * 2 + 1];
}
}
}