目錄
一、線段樹（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; // 返回總面積
}三、總結
-
線段樹：適用于區間查詢和更新操作，常用于處理動態區間問題。
-
掃描線：適用于處理幾何問題，特別是與平面中的矩形、線段等相關的問題。
????????這兩種算法思想在解決特定類型的問題時非常有效，理解它們的原理和應用場景有助于在編程競賽和實際開發中更好地解決問題。
)
)
