线段树与扫描线 —— 详解算法思想及其C++实现

目录

一、线段树（Segment Tree）

基本概念

结构

操作

示例代码

二、扫描线（Sweep Line）

基本概念

应用场景

示例代码（矩形面积并集）

三、总结

---

一、线段树（Segment Tree）

基本概念

        线段树是一种用于处理区间查询和更新操作的数据结构，常用于解决区间最值、区间和等问题。它将一个区间划分为若干个子区间，每个子区间对应树中的一个节点。

结构

• 叶子节点：代表数组中的单个元素。

• 内部节点：代表数组中的某个区间，通常是其子节点的并集。

操作

1. 构建（Build）：从数组构建线段树，时间复杂度为 O(n)O(n)。

2. 查询（Query）：查询某个区间的信息（如最小值、最大值、和等），时间复杂度为 O(log⁡n)O(logn)。

3. 更新（Update）：更新数组中的某个元素，并相应地更新线段树，时间复杂度为 O(log⁡n)O(logn)。

示例代码

#include <vector>  // 引入向量容器，用于动态数组
#include <algorithm>  // 引入算法库，提供常用算法（如排序）class SegmentTree {
private:std::vector<int> tree;  // 线段树的数组表示int n;  // 原始数组的大小// 构建线段树的递归函数void build(const std::vector<int>& arr, int node, int start, int end) {if (start == end) {  // 如果当前区间只有一个元素tree[node] = arr[start];  // 直接将数组值赋给叶子节点} else {int mid = (start + end) / 2;  // 计算区间的中点build(arr, 2 * node + 1, start, mid);  // 递归构建左子树build(arr, 2 * node + 2, mid + 1, end);  // 递归构建右子树tree[node] = tree[2 * node + 1] + tree[2 * node + 2];  // 当前节点的值为左右子节点的和}}// 查询区间和的递归函数int query(int node, int start, int end, int l, int r) {if (r < start || end < l) {  // 如果查询区间与当前区间无交集return 0;  // 返回0，表示无贡献}if (l <= start && end <= r) {  // 如果当前区间完全包含在查询区间内return tree[node];  // 返回当前节点的值}int mid = (start + end) / 2;  // 计算区间的中点// 递归查询左右子树，并将结果相加return query(2 * node + 1, start, mid, l, r) + query(2 * node + 2, mid + 1, end, l, r);}// 更新数组中某个元素的递归函数void update(int node, int start, int end, int idx, int val) {if (start == end) {  // 如果当前区间只有一个元素tree[node] = val;  // 直接更新叶子节点的值} else {int mid = (start + end) / 2;  // 计算区间的中点if (idx <= mid) {  // 如果目标位置在左子树update(2 * node + 1, start, mid, idx, val);  // 递归更新左子树} else {  // 如果目标位置在右子树update(2 * node + 2, mid + 1, end, idx, val);  // 递归更新右子树}tree[node] = tree[2 * node + 1] + tree[2 * node + 2];  // 更新当前节点的值为左右子节点的和}}public:// 构造函数，初始化线段树SegmentTree(const std::vector<int>& arr) {n = arr.size();  // 获取原始数组的大小tree.resize(4 * n);  // 为线段树分配空间，通常为4倍数组大小build(arr, 0, 0, n - 1);  // 构建线段树}// 查询区间和的公共接口int query(int l, int r) {return query(0, 0, n - 1, l, r);  // 调用私有查询函数}// 更新数组中某个元素的公共接口void update(int idx, int val) {update(0, 0, n - 1, idx, val);  // 调用私有更新函数}
};

二、扫描线（Sweep Line）

基本概念

        扫描线算法是一种用于处理几何问题的算法，通常用于计算平面中多个矩形的并集面积、线段交点等问题。其核心思想是通过一条虚拟的线（通常是垂直于x轴或y轴的线）在平面上扫描，并在扫描过程中处理与线相交的几何对象。

应用场景

• 矩形面积并集：计算多个矩形的总面积。

• 线段交点：找出所有线段的交点。

• 多边形面积：计算多边形的面积。

示例代码（矩形面积并集）

#include <vector>  // 引入向量容器，用于动态数组
#include <algorithm>  // 引入算法库，提供常用算法（如排序）
#include <set>  // 引入集合容器，用于存储和管理活动的区间// 定义事件结构体，表示矩形的开始或结束事件
struct Event {int x, y1, y2;  // x坐标，y1和y2表示矩形的垂直区间bool isStart;  // 标记事件是矩形的开始还是结束Event(int x, int y1, int y2, bool isStart) : x(x), y1(y1), y2(y2), isStart(isStart) {}
};// 比较函数，用于对事件按x坐标排序
bool compareEvents(const Event& a, const Event& b) {return a.x < b.x;  // 按x坐标升序排列
}// 计算矩形面积并集的函数
int calculateArea(const std::vector<std::vector<int>>& rectangles) {std::vector<Event> events;  // 存储所有事件（矩形的开始和结束）for (const auto& rect : rectangles) {// 添加矩形的开始事件（左边界）events.emplace_back(rect[0], rect[1], rect[3], true);// 添加矩形的结束事件（右边界）events.emplace_back(rect[2], rect[1], rect[3], false);}// 对所有事件按x坐标排序std::sort(events.begin(), events.end(), compareEvents);std::multiset<std::pair<int, int>> activeIntervals;  // 存储当前活动的垂直区间int prevX = 0;  // 前一个事件的x坐标int totalArea = 0;  // 总面积// 遍历所有事件for (const auto& event : events) {int currentX = event.x;  // 当前事件的x坐标if (!activeIntervals.empty()) {  // 如果有活动的区间int height = 0;  // 当前扫描线覆盖的总高度int prevY = -1;  // 前一个区间的y坐标// 遍历所有活动区间，计算覆盖的高度for (const auto& interval : activeIntervals) {if (prevY == -1) {  // 如果是第一个区间prevY = interval.first;  // 初始化prevY}if (interval.first > prevY) {  // 如果当前区间与前一个区间不重叠height += interval.first - prevY;  // 累加高度}prevY = std::max(prevY, interval.second);  // 更新prevY}// 计算当前扫描线与前一个扫描线之间的面积，并累加到总面积totalArea += height * (currentX - prevX);}prevX = currentX;  // 更新prevXif (event.isStart) {  // 如果是矩形的开始事件activeIntervals.insert({event.y1, event.y2});  // 将区间加入活动集合} else {  // 如果是矩形的结束事件activeIntervals.erase(activeIntervals.find({event.y1, event.y2}));  // 将区间从活动集合中移除}}return totalArea;  // 返回总面积
}

三、总结

• 线段树：适用于区间查询和更新操作，常用于处理动态区间问题。

• 扫描线：适用于处理几何问题，特别是与平面中的矩形、线段等相关的问题。

        这两种算法思想在解决特定类型的问题时非常有效，理解它们的原理和应用场景有助于在编程竞赛和实际开发中更好地解决问题。