线段树 学习笔记

发表于 | 分类于 | | + s

模板及讲解

什么时候要用线段树?
1、统计量可合并
2、修改量可合并
3、通过修改量可直接修改统计量
⼀句话: 满⾜区间加法即可使用线段树维护信息

常见题型

1、线段树合并区间
在区间维护若干个值。
例题：BZOJ 1593
2、离散化
解：运用二分查找进行离散化。1、全部顶点加入数组 2、排序去重 3、值相差大于1的中间插一个值(直接在末尾插$val[i-1]+1$, 再作sort即可)
例题：Hdu 1542

3、动态开点线段树
例题：BZOJ 3531
4、权值线段树
例题：poj 2299
5、扫描线
Q：给出n个矩形，求他们的面积并/周长并。
例题：Hdu 1542，Hdu 1828
6、线段树合并(主席树) / 线段树分裂
合并：Bzoj 1926, 主席树等
分裂：Bzoj 4552
7、线段树优化连边
例题：BZOJ 2143

相关代码

区间修改，区间查询：Luogu 3372

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)

namespace flyinthesky {  

    const LL MAXN = 100000 + 5;

    LL n, m, a[MAXN];
    LL sumv[MAXN * 4], addv[MAXN * 4];

    void pushup(LL o) {
        sumv[o] = sumv[lc] + sumv[rc];
    }
    void pushdown(LL o, LL len) {
        if (len == 1) return ;
        if (addv[o]) {
            addv[lc] += addv[o], addv[rc] += addv[o];
            sumv[lc] += addv[o] * (len - (len / 2)), sumv[rc] += addv[o] * (len / 2);
            addv[o] = 0;
        }
    }
    void build(LL o, LL l, LL r) {
        if (l == r) {sumv[o] = a[l]; return ;} else build(lc, l, M), build(rc, M + 1, r);
        pushup(o);
    }
    void update(LL o, LL l, LL r, LL x, LL y, LL v) {
        pushdown(o, r - l + 1);
        if (x <= l && r <= y) {addv[o] += v, sumv[o] += v * (r - l + 1); return ;}
        if (x <= M) update(lc, l, M, x, y, v); 
        if (M < y) update(rc, M + 1, r, x, y, v);
        pushup(o);
    }
    LL query(LL o, LL l, LL r, LL x, LL y) {
        pushdown(o, r - l + 1);
        if (x <= l && r <= y) return sumv[o];
        LL ans = 0;
        if (x <= M) ans += query(lc, l, M, x, y); 
        if (M < y) ans += query(rc, M + 1, r, x, y);
        return ans;
    }

    void clean() {
    }
    int solve() {
        scanf("%lld%lld", &n, &m);
        clean();
        for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);
        build(1, 1, n);
        while (m--) {
            LL ty; scanf("%lld", &ty);
            if (ty == 1) {
                LL x, y, k; scanf("%lld%lld%lld", &x, &y, &k);
                update(1, 1, n, x, y, k);
            } else {
                LL x, y; scanf("%lld%lld", &x, &y);
                printf("%lld\n", query(1, 1, n, x, y));
            }
        }
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

单点修改，区间查询：Bzoj 1012

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)

namespace flyinthesky {  

    const LL MAXN = 200000 + 5;

    LL now, n, d;
    LL maxv[MAXN * 4];
    char s[4];

    void pushup(LL o) {maxv[o] = max(maxv[lc], maxv[rc]);}
    void build(LL o, LL l, LL r) {
        maxv[o] = 0;
        if (l == r) return ; else build(lc, l, M), build(rc, M + 1, r);
        pushup(o);
    }
    LL query(LL o, LL l, LL r, LL x, LL y) {
        if (x <= l && r <= y) return maxv[o];
        LL ans = 0;
        if (x <= M) ans = max(ans, query(lc, l, M, x, y));
        if (M < y) ans = max(ans, query(rc, M + 1, r, x, y));
        return ans;
    }
    void update(LL o, LL l, LL r, LL p, LL v) {
        if (l == r) {maxv[o] = v; return ;}
        if (p <= M) update(lc, l, M, p, v); else if (M < p) update(rc, M + 1, r, p, v);
        pushup(o);
    } 

    void clean() {
        now = 0;
    }
    int solve() {
        scanf("%lld%lld", &n, &d);
        clean();
        build(1, 1, n);
        LL t = 0;
        for (LL x, i = 1; i <= n; i++) {
            scanf("%s%lld", s, &x);
            if (s[0] == 'A') update(1, 1, n, ++now, (x + t) % d); 
            else printf("%lld\n", t = query(1, 1, n, now - x + 1, now));
        }
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------