欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

备战NOIP——模板复习1

程序员文章站 2022-03-23 09:22:36
...

目录

线段树模板

单点修改区间查询

区间修改单点查询

区间修改区间查询


 

这里只有模板,并不作讲解,仅为路过的各位做一个参考以及用做自己复习的资料,转载注明出处。

线段树模板

 

单点修改区间查询

/*Copyright: Copyright (c) 2018
*Created on 2018-10-28  
*Author: 十甫
*Version 1.0 
*Title: 线段树1
*Time: 9 mins
*/ 

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 10005;
#define ls i * 2
#define rs i * 2 + 1

struct node {
    int l, r, val;
} data[maxn * 4];
inline void push_up(int i) {
    data[i].val = data[ls].val + data[rs].val;
}
inline void build(int i, int l, int r) {
    data[i] = (node) {l, r, 0};
    if(l == r) {
        scanf("%d", &data[i].val);
        return;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid), build(rs, mid + 1, r);
    push_up(i);
}
inline void add(int i, int pos, int k) {
    if(data[i].l == data[i].r) {
        data[i].val += k;
        return;
    }
    int mid = (data[i].l + data[i].r) / 2;
    if(pos <= mid) add(ls, pos, k);
    else add(rs, pos, k);
    push_up(i);
}
inline int query(int i, int l, int r) {
    if(l <= data[i].l && r >= data[i].r) {
        return data[i].val;
    }
    int mid = (data[i].l + data[i].r) / 2;
    if(r <= mid) return query(ls, l, r);
    else if(l > mid) return query(rs, l, r);
    else return query(ls, l, mid) + query(rs, mid + 1, r);
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while(m--) {
        int man;
        scanf("%d", &man);
        if(man) {
            int pos, k;
            scanf("%d%d", &pos, &k);
            add(1, pos, k);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", query(1, l, r));
        }
    }
    return 0;
}

 

区间修改单点查询

/*Copyright: Copyright (c) 2018
*Created on 2018-10-28  
*Author: 十甫
*Version 1.0 
*Title: 线段树2
*Time: 9 mins
*/ 
#include<iostream>
#include<cstdio>
using namespace std;
const int size = 10005;
#define ls i * 2
#define rs i * 2 + 1

struct node {
    int l, r, val;
} data[size * 4];
inline void push_up(int i) {
    data[i].val = data[ls].val + data[rs].val;
}
int tmp1 = 0, tmp2 = 0;
inline void build(int i, int l, int r) {
    data[i] = (node) {l, r, 0};
    if(l == r) {
        scanf("%d", &tmp2);
        data[i].val = tmp2 - tmp1, tmp1 = tmp2;
        return;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid), build(rs, mid + 1, r);
    push_up(i);
}
inline void add(int i, int pos, int k) {
    if(data[i].l == data[i].r) {
        data[i].val += k;
        return;
    }
    int mid = (data[i].l + data[i].r) / 2;
    if(pos <= mid) add(ls, pos, k);
    else add(rs, pos, k);
    push_up(i);
}
inline int query(int i, int l, int r) {
    if(l <= data[i].l && r >= data[i].r) {
        return data[i].val;
    }
    int mid = (data[i].l + data[i].r) / 2;
    if(r <= mid) return query(ls, l, r);
    else if(l > mid) return query(rs, l, r);
    else return query(ls, l, mid) + query(rs, mid + 1, r);
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while(m--) {
        int man;
        scanf("%d", &man);
        if(man) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            add(1, l, k);
            if(r < n) add(1, r + 1, -k);
        } else {
            int pos;
            scanf("%d", &pos);
            printf("%d\n", query(1, 1, pos));
        }
    }
    return 0;
}

 

区间修改区间查询

/*Copyright: Copyright (c) 2018
*Created on 2018-10-28  
*Author: 十甫
*Version 1.0 
*Title: 线段树3
*Time: 12 mins
*/ 
#include<iostream>
#include<cstdio>
using namespace std;
const int size = 10005;
#define ls i * 2
#define rs i * 2 + 1

struct node {
    int l, r, val, tag;
    inline int len() {
        return r - l + 1;
    }
} data[size * 4];

inline void push_up(int i) {
    data[i].val = data[ls].val + data[rs].val;
}
inline void push_down(int i) {
    data[ls].val += data[ls].len() * data[i].tag, data[rs].val += data[i].len() * data[rs].tag;
    data[ls].tag += data[i].tag, data[rs].tag += data[i].tag;
    data[i].tag = 0;
}
inline void build(int i, int l, int r) {
    data[i] = (node) {l, r, 0, 0};
    if(l == r) {
        scanf("%d", &data[i].val);
        return;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid), build(rs, mid + 1, r);
    push_up(i);
}
inline void add(int i, int l, int r, int k) {
    if(l <= data[i].l && r >= data[i].r) {
        data[i].tag += k, data[i].val += data[i].len() * k;
        return;
    }
    int mid = (data[i].l + data[i].r) / 2;
    if(r <= mid) add(ls, l, r, k);
    else if(l > mid) add(rs, l, r, k);
    else add(ls, l, mid, k), add(rs, mid + 1, r, k);
    push_up(i);
}
inline int query(int i, int l, int r) {
    if(l >= data[i].l && r >= data[i].r) {
        return data[i].val;
    }
    int mid = (data[i].l + data[i].r) / 2;
    push_down(i);
    if(r <= mid) return query(ls, l, r);
    else if(l > mid) return query(rs, l, r);
    else return query(ls, l, mid) + query(rs, mid + 1, r);
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while(m--) {
        int man;
        scanf("%d", &man);
        if(man) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            add(1, l, r, k);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", query(1, l, r));
        }
    }
    return 0;
}