线段树

时间：2024-03-17 10:24:25

时间复杂度：O(logn)
解决问题：单点修改，区间查询，区间修改（要懒标记）
操作：1.pushup: 用子节点信息更新当前节点信息，2.build: 在一段区间上初始化线段树，3.modify: 修改，4.query: 查询
最多 4 * n 个点
x 的父节点: x / 2（x >> 1）
左儿子 2 * x（x << 1）
右儿子 2 * x + 1（x << 1 | 1）
在这里插入图片描述

1.动态求连续区间和

维护区间和

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int w[N];
int n, m;
struct Node{
    int l, r;
    // 维护区间和
    int sum;
}tr[4 * N];

// 把信息往上传递
void pushup(int x){
    tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;
}

// 根节点，区间左端点，区间右端点
void build(int x, int l, int r){
	// 是叶子节点就返回
    if(l == r) tr[x] = {l, r, w[r]};
    else{
    // 不是叶子节点就裂开
        tr[x] = {l, r};
        int mid = (l + r) / 2;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        pushup(x);
    }
}

int query(int x, int l, int r){
    if(tr[x].l >= l && tr[x].r <= r) return tr[x].sum;
    else{
        int mid = (tr[x].l + tr[x].r) / 2;
        int sum = 0;
        if(l <= mid) sum = query(x << 1, l, r);
        if(r > mid) sum += query(x << 1 | 1, l, r);
        return sum;
    }
}

// 根节点，插入位置，插入值
void modify(int x, int a, int b){
    if(tr[x].l == tr[x].r) tr[x].sum += b;
    else{
        int mid = (tr[x].l + tr[x].r) / 2;
        if(a <= mid) modify(x << 1, a, b);
        else modify(x << 1 | 1, a, b);
        pushup(x);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    build(1, 1, n);
    
    int k, a, b;
    while(m--){
        scanf("%d%d%d", &k, &a, &b);
        if(k == 0) printf("%d\n", query(1, a, b));
        else modify(1, a, b);
    }
    return 0;
}

2.数列区间最大值

在这里插入图片描述
维护区间最大值

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int w[N];
int n, m;
struct Node{
    int l, r;
    // 维护区间最大值
    int sum;
}tr[4 * N];

void pushup(int x){
    tr[x].sum = max(tr[x << 1].sum, tr[x << 1 | 1].sum);
}

void build(int x, int l, int r){
    if(l == r) tr[x] = {l, r, w[r]};
    else{
        tr[x] = {l, r};
        int mid = (l + r) / 2;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        pushup(x);
    }
}

int query(int x, int l, int r){
    if(tr[x].l >= l && tr[x].r <= r) return tr[x].sum;
    else{
        int mid = (tr[x].l + tr[x].r) / 2;
        int res = INT32_MIN;
        // 判断递归到哪个儿子
        if(l <= mid) res = query(x << 1, l, r);
        if(r > mid) res = max(res, query(x << 1 | 1, l, r));
        return res;
    }
}

void modify(int x, int a, int b){
    if(tr[x].l == tr[x].r) tr[x].sum += b;
    else{
        int mid = (tr[x].l + tr[x].r) / 2;
        if(a <= mid) modify(x << 1, a, b);
        else modify(x << 1 | 1, a, b);
        pushup(x);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    build(1, 1, n);
    int a, b;
    while(m--){
        scanf("%d%d", &a, &b);
        printf("%d\n", query(1, a, b));
    }
    return 0;
}

3.油漆面积

在这里插入图片描述
在这里插入图片描述
扫描线法：还可以是斜着矩阵、三角形、圆形
非常特殊的线段树，延迟更新，不考虑父节点的信息，只考虑子节点的信息
懒标记可以不往下传，所以非常特殊
成对，先加后减，cnt >= 0，只查询根节点
在这里插入图片描述
这个线段树是竖着的区间

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10;
int n;
struct Node1{
    int l, r;
    // 存储当前区间被覆盖的次数
    int cnt;
    // 存储当前区间的长度，竖着的区间
    int len;
}tr[4 * N];

struct Node2{
    int x, y1, y2;
    // 存储 1 或 -1，表示成对出现的区间
    int k;
    // 根据 x 排序
    bool operator<(const Node2 &t)const{
        return x < t.x;
    }
}seg[2 * N];

// 往上更新根节点
void pushup(int x){
    // 如果被覆盖过，那就更新长度，这个要放在前面
    if(tr[x].cnt > 0) tr[x].len = tr[x].r - tr[x].l + 1;
    // 此时为一条线
    else if(tr[x].l == tr[x].r) tr[x].len = 0;
    // 否则递归处理
    else tr[x].len = tr[x << 1].len + tr[x << 1 | 1].len;
}

void build(int x, int l, int r){
    if(l == r) tr[x] = {l, r};
    else{
        tr[x] = {l, r};
        int mid = (l + r) / 2;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
    }
}

void modify(int x, int l, int r, int k){
    if(tr[x].l >= l && tr[x].r <= r){
        // 更新被覆盖的次数
        tr[x].cnt += k;
        // 传递给根节点
        pushup(x);
    }else{
        int mid = (tr[x].l + tr[x].r) / 2;
        if(l <= mid) modify(x << 1, l, r, k);
        if(r > mid) modify(x << 1 | 1, l, r, k);
        pushup(x);
    }
}

int main(){
    scanf("%d", &n);
    int x1, y1, x2, y2, m = 0;
    for(int i = 0; i < n; i++){
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        seg[m++] = {x1, y1, y2, 1};
        seg[m++] = {x2, y1, y2, -1};
    }
    sort(seg, seg + m);
    build(1, 0, 10000);
    int res = 0;
    for(int i = 0; i < m; i++){
        // 每次都会更新根节点的长度，tr[1].len 就是竖着的区间长度
        if(i) res += tr[1].len * (seg[i].x - seg[i - 1].x);
        modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k);
    }
    printf("%d", res);
    return 0;
}

相关文章