线段树知识点及其应用

线段树 (Segment Tree)

1. 引入

线段树 是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 $O(\log N)$ 的时间复杂度内实现以下操作：

• 单点修改 (Point Update)
• 区间修改 (Range Update)
• 区间查询 (Range Query)：如区间求和、求区间最大值/最小值 (RMQ) 等。

2. 基本原理

线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右子节点的信息来维护父节点的信息。

结构示意

线段树是一棵二叉树，对于一个区间 $[L, R]$：

• 若 $L = R$，则该节点为叶子节点，存储数组中对应位置的值。
• 若 $L < R$，则将区间分为 $[L, mid]$ 和 $[mid+1, R]$ 两个子区间，其中 $mid = \lfloor (L+R)/2 \rfloor$。

3. C++ 代码模板

以下是一个基本的线段树模板（以维护区间和为例）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll tree[MAXN * 4]; 
ll arr[MAXN];
// 建树 Build: O(N)
void build(int p, int l, int r) {
    if (l == r) {
        tree[p] = arr[l];
    } else {
        int mid = (l + r) / 2;
        build(p<<1, l, mid);
        build(p<<1|1, mid + 1, r);
        // Push Up: 向上更新父节点
        tree[p] = tree[p<<1] + tree[p<<1|1];
    }
}
// 单点修改 Update: O(log N)
void update(int p, int l, int r, int idx, int val) {
    if (l == r) {
        arr[idx] += val;
        tree[p] += val;
    } else {
        int mid = (l + r) / 2;
        if (l <= idx && idx <= mid) {
            update(p<<1, l, mid, idx, val);
        } else {
            update(p<<1|1, mid + 1, r, idx, val);
        }
        tree[p] = tree[p<<1] + tree[p<<1|1];
    }
}
// 区间查询 Query: O(log N)
ll query(int p, int l, int r, int l, int r) {
    if (r < l || r < l) {
        return 0; // 返回不影响结果的值
    }
    if (l <= l && r <= r) {
        return tree[p];
    }
    int mid = (l + r) / 2;
    ll p1 = query(p<<1, l, mid, l, r);
    ll p2 = query(p<<1|1, mid + 1, r, l, r);
    return p1 + p2;
}

4. 复杂度分析

• 空间复杂度：线段树需要开 $4N$ 的空间，即 $O(N)$。
• 时间复杂度：
  • 建树：$O(N)$
  • 单点修改：$O(\log N)$
  • 区间查询：$O(\log N)$

5. 进阶应用：扫描线算法 (Sweep Line)

问题描述：给定平面上 $n$ 个矩形，求它们的面积并。
本题对应 luoguP8648
解题思路：
使用扫描线算法，将矩形的左右竖边作为扫描线，按 $x$ 坐标排序。从左向右扫描，使用线段树维护 $y$ 轴方向上的覆盖长度。

• 遇到矩形左边（$w=1$），区间覆盖次数 $+1$。
• 遇到矩形右边（$w=-1$），区间覆盖次数 $-1$。
• 线段树维护当前被覆盖的 $y$ 轴总长度 len。
• 每次扫描线移动时，累加面积 res += tree[1].len * (seg[i].x - seg[i-1].x)。

代码示例：

#include<bits/stdc++.h> 
using namespace std; 
typedef long long ll; 
const int N=1e4+10; 
int res=0; 
struct Segment{     // 扫描线（矩形竖边）
    int x, y1, y2; 
    int w;          // w=1：矩形左边界，w=-1：矩形右边界 
    bool operator<(const Segment& c) const{ 
        return x < c.x;      
    } 
} seg[N<<1]; 
struct Node{        // 线段树节点 
    int l, r; 
    int cnt;        // 当前区间被覆盖的次数
    int len;        // 当前区间被覆盖的有效长度
} tree[N<<2]; 
void push_up(int p){ // 维护区间覆盖长度 
    if(tree[p].cnt > 0){ 
        // 如果该区间被整体覆盖，长度就是 y[r] - y[l] + 1 
        tree[p].len = tree[p].r - tree[p].l + 1;   
    } 
    else if(tree[p].l == tree[p].r) {
        tree[p].len = 0; // 叶子节点
    }
    else {
        tree[p].len = tree[p<<1].len + tree[p<<1|1].len; // 根节点长度为子节点长度和 
    }
} 
void build(int p, int l, int r){ // 建树 
    tree[p] = {l, r, 0, 0}; 
    if(l == r) return; 
    int mid = (l + r) >> 1; 
    build(p<<1, l, mid); 
    build(p<<1|1, mid+1, r); 
} 
void modify(int p, int l, int r, int d){ 
    if(tree[p].l >= l && tree[p].r <= r){ // 如果当前节点区间完全在查询区间内 
        tree[p].cnt += d; 
        push_up(p); 
    } else { 
        int mid = (tree[p].l + tree[p].r) >> 1; 
        if(l <= mid) modify(p<<1, l, r, d); 
        if(r > mid) modify(p<<1|1, l, r, d); 
        push_up(p);     
    } 
} 
int main(){ 
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    int n; 
    cin >> n; 
    int m = 0; 
    for(int i = 0; i < n; i++){ 
        int x1, y1, x2, y2; 
        cin >> x1 >> y1 >> x2 >> y2; 
        seg[m++] = {x1, y1, y2, 1}; 
        seg[m++] = {x2, y1, y2, -1}; 
    } 
    sort(seg, seg + m); // 注意：seg是数组，需指定排序范围
    // 假设坐标范围较小(0-10000)，直接建树
    build(1, 0, 10000); 
    for(int i = 0; i < m; i++){ 
        if(i > 0){ 
            res += tree[1].len * (seg[i].x - seg[i-1].x); 
        } 
        // 区间处理技巧：将 [y1, y2] 视为 [y1, y2-1] 进行覆盖，
        // 这样叶子节点 i 代表区间 [i, i+1]
        modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].w); 
    } 
    cout << res << endl; 
    return 0; 
}