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

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

article 2025/3/25 13:28: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;  // 更新prevX

        if (event.isStart) {  // 如果是矩形的开始事件
            activeIntervals.insert({event.y1, event.y2});  // 将区间加入活动集合
        } else {  // 如果是矩形的结束事件
            activeIntervals.erase(activeIntervals.find({event.y1, event.y2}));  // 将区间从活动集合中移除
        }
    }

    return totalArea;  // 返回总面积
}