Voldemort's blog

Voldemort's blog

我好菜啊

线段树学习笔记

posted on 2020-01-24 17:42:32 | under 笔记 |

写在前面

线段树是一种特别玄学的数据结构,它可以维护(优化)一些线段(区间)的算法,使其的时间复杂度由 $\Theta(n)$变成 $\Theta(\log n)$,无疑是一种完美的优化。

线段树长啥样?

大概长这样:

解释一下这个图:
$l,r$表示这个节点所对应的区间,比如节点1所对应的区间为 $[1,4]$,上面的数字代表着节点编号。

线段树的几个性质

仔细观察上图得:
1:左孩子的编号为父亲的两倍

写出代码:

int lchild(int root) {  //root代表父亲节点
    return root * 2;  //返回左孩子的节点
}

2:右孩子的编号为父亲的两倍加一

代码:

int rchild(int root) {  //root代表父亲节点
    return root * 2 + 1;  //返回右孩子的节点
}

上面两条性质我们可以推广到任意的完全二叉树,接下来是线段树独有的特性
3::左孩子管理的区间是 $[l,\frac{l + r}{2}]$( $l,r$表示父亲管理的区间的左边界和右边界)
4:右孩子管理的区间是 $[\frac{l + r}{2} + 1,r]$
5:父亲节点的的权值由子节点取得

例题分析

【模板】线段树 1

首先我们先把样例搞下来:

快把我画死了
我们发现这里多了一个 $pre$,这是干嘛用的?
其实, $pre$表示的就是 $[l,r]$的区间和,也就是该节点的权值。
那我们开始构建我们的线段树吧!!

第一步,存下这个线段树:

namespace SegmentTree {
    struct Seg {
        int l,r;
        long long lazy;
        long long pre;
    };

    Seg Tree[N * 4];

    int lchild(int root) {
        return root * 2;
    }
    int rchild(int root) {
        return root * 2 + 1;
    }
};  

那个 $lazy$先不去管它,后面有用。
其实线段树不需要开四倍空间,三倍就够了,确切的说是 $2\times n + 1$,不过不要这么小气。

第二步,建树(build操作)

这个怎么做呢?
1:确定每个节点控制的区间范围,这个很简单对吧?
2:确定每一个节点的值,这个我们分类讨论。如果它是一个叶子节点,那么它的权值就是他控制的端点 $a[l]$;如果它不是子节点,那么它的值由它的两个子节点的权值确定。
没了。

建树操作 $code$

void build(int root,int l,int r) {
    Tree[root].l = l;  //确定左右端点
    Tree[root].r = r;
    if(l == r) {  //如果它是叶子节点
        Tree[root].pre = a[l];  //控制的就是a[l]
        return;  //注意return
    }
    int mid = (l + r) >> 1;  //取中,同性质
    build(lchild(root),l,mid);  //继续构造两个儿子
    build(rchild(root),mid + 1,r);
    Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;  //父节点的值由子节点确定
}  

这一步必须好好理解,不然后面的区间修改和查询你就看不懂了。

第三步,区间修改(update操作)

这个比建树难很多,那个 $lazy$有什么用你们马上就要知道了。
这个我们用图来感性理解一下:

其中蓝色表示线段树节点控制的范围,红色表示我们要找的范围。
在这种情况下,节点控制的所有数是不是都要改?包括它的孩子也要做改动?
但是我们在这里不管这么多,改动孩子我们交给懒标记 lazy 就好了, lazy 我们过一下讲。再看这张图:

这个怎么办?
很明显,我们需要改动的只有蓝l到红r的数,这个我们让孩子来做。

好了,我们开始讲 lazy

正如之间所说,它是一个懒标记,每次我们改动了一个节点的数时,就写一句:

Tree[root].lazy += k;

完了,剩下来的是让孩子去做吧。
怎么让孩子做呢?
我们写一个 push_down 函数,这个我们跟着代码来理解。

void push_down(int root) {  //传入父节点编号
    if(Tree[root].lazy) {
        Tree[lchild(root)].pre += Tree[root].lazy * (Tree[lchild(root)].r - Tree[lchild(root)].l + 1);  //下传懒标记,父亲懒标记里加的东西儿子都没有加过
        Tree[rchild(root)].pre += Tree[root].lazy * (Tree[rchild(root)].r - Tree[rchild(root)].l + 1);
        Tree[lchild(root)].lazy += Tree[root].lazy;  //两个孩子传了懒标记,现在继续下传
        Tree[rchild(root)].lazy += Tree[root].lazy;
        Tree[root].lazy = 0;  //父亲不欠左右孩子了,懒标记清0
    }
}

这样就好理解了吧!
理解了之后,我们就可以继续讲 update 了,我们分情况来讨论。
1.给定现结点的左右区间记为 $[l,r]$,我们要找的区间记为 $[L,R]$,若 $[l,r] \subseteq [L,R]$,那么 $[l,r]$全加
2.如果 $[l,\frac{l+r}{2}] \subseteq [L,R]$,让左孩子操作
3.如果 $[\frac{l+r}{2} + 1,r] \subseteq [L,R]$,让右孩子操作
放代码

void update(int root,int l,int r,int k) {
    if(Tree[root].l >= l && Tree[root].r <= r) {
        Tree[root].pre += (long long)k * (Tree[root].r - Tree[root].l + 1);
        Tree[root].lazy += k;
        return;
    }
    push_down(root);
    int mid = (Tree[root].l + Tree[root].r) >> 1;
    if(l <= mid) update(lchild(root),l,r,k);
    if(r > mid) update(rchild(root),l,r,k);
    Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;
}

还行吧,感受到算法的奇妙了吗?
好好理解,重点是如何传 lazy 和控制区间。

第四步,区间求和(query 操作)

接下来我们讲 query,讲完了我们这道题就做完了。
其实 queryupdate 差不了多少,看下面:
1. 若该线段树所控制的区间在目标区间内,则直接加上控制的这个值
2. 在左边或者右边的话同 update 操作
最后定义一个 ans 记录和就好了!!

放代码

long long query(int root,int l,int r) {
    if(Tree[root].l >= l && Tree[root].r <= r) return Tree[root].pre;
    push_down(root);
    int mid = (Tree[root].l + Tree[root].r) >> 1;
    long long cnt = 0;
    if(l <= mid) cnt += query(lchild(root),l,r);
    if(r > mid) cnt += query(rchild(root),l,r);
    return cnt;
}

所以我们就做完了线段树的模板1,放代码!!

#include <bits/stdc++.h>
using namespace std;

namespace IO {
    #pragma GCC target("avx")
    #pragma GCC optimize("Og")
    #pragma GCC optimize("Ofast")

    template<class T>
    inline void read(T& x) {
        x = 0;
        int p = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9') {
            if(ch == '-') p = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9') {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        x = x * p;
    }

    template<class T>
    inline void write(T x) {
        if(x < 0) {
            x = -x;
        }
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
};

using namespace IO;

const int N = 100010;

int a[N];
int n,q;

namespace SegmentTree {  //线段树
    struct Seg {
        int l,r;
        long long lazy;
        long long pre;
    };

    Seg Tree[N * 4];

    int lchild(int root) {
        return root * 2;
    }
    int rchild(int root) {
        return root * 2 + 1;
    }

    void build(int root,int l,int r) {
        Tree[root].l = l;
        Tree[root].r = r;
        if(l == r) {
            Tree[root].pre = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lchild(root),l,mid);
        build(rchild(root),mid + 1,r);
        Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;
    }

    void push_down(int root) {
        if(Tree[root].lazy) {
            Tree[lchild(root)].pre += Tree[root].lazy * (Tree[lchild(root)].r - Tree[lchild(root)].l + 1);
            Tree[rchild(root)].pre += Tree[root].lazy * (Tree[rchild(root)].r - Tree[rchild(root)].l + 1);
            Tree[lchild(root)].lazy += Tree[root].lazy;
            Tree[rchild(root)].lazy += Tree[root].lazy;
            Tree[root].lazy = 0;
        }
    }

    void update(int root,int l,int r,int k) {
        if(Tree[root].l >= l && Tree[root].r <= r) {
            Tree[root].pre += (long long)k * (Tree[root].r - Tree[root].l + 1);
            Tree[root].lazy += k;
            return;
        }
        push_down(root);
        int mid = (Tree[root].l + Tree[root].r) >> 1;
        if(l <= mid) update(lchild(root),l,r,k);
        if(r > mid) update(rchild(root),l,r,k);
        Tree[root].pre = Tree[lchild(root)].pre + Tree[rchild(root)].pre;
    }

    long long query(int root,int l,int r) {
        if(Tree[root].l >= l && Tree[root].r <= r) return Tree[root].pre;
        push_down(root);
        int mid = (Tree[root].l + Tree[root].r) >> 1;
        long long cnt = 0;
        if(l <= mid) cnt += query(lchild(root),l,r);
        if(r > mid) cnt += query(rchild(root),l,r);
        return cnt;
    }
};

using namespace SegmentTree;  //使用这个namespace

int main() {
    read(n);read(q);
    for(int i = 1;i <= n;i++) {
        read(a[i]);
    }
    build(1,1,n);
    for(int i = 1;i <= q;i++) {
        int opt;
        read(opt);
        if(opt == 1) {
            int l,r,k;
            read(l);read(r);read(k);
            update(1,l,r,k);
        }else {
            int l,r;
            read(l);read(r);
            write(query(1,l,r));puts("");
        }
    }
    return 0;
}