当前位置：首页 > news >正文

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

news 2025/3/26 3:46:32

一、线段树（Segment Tree）

基本概念

结构

操作

示例代码

二、扫描线（Sweep Line）

基本概念

应用场景

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

三、总结

一、线段树（Segment Tree）

基本概念

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

结构

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

操作

构建（Build）：从数组构建线段树，时间复杂度为 O(n)O(n)。
查询（Query）：查询某个区间的信息（如最小值、最大值、和等），时间复杂度为 O(log⁡n)O(logn)。
更新（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;  // 返回总面积
}