【AC军团周报（第二周）第二篇】线段树从入门到入土【2】

本文章连载AC军团周报

-> 线段树：从入门到入土【2】

前言：

第二期了，我们要把上一期留下的锅补一下。

这一期的内容主要是懒标记，处理区间修改的问题。

我们最后再分析一下线段树时间复杂度

一、线段树入门（续）

我们上一期学习了线段树的入门操作，主要是进行建树，区间查询，单点修改。我们来仔细回想一下吧。

……………………回想时间……………………

如果你回想完了，就再思考一下上一节留下的问题：

如何做到区间修改

我们考虑时间复杂度的话一个一个进行单点修改是肯定不行的（之后我们会分析时间复杂度），你也不能一个一个加。

我们考虑我们线段树维护的是什么

是不是线段上的区间和？

假如我们给一个区间中的每个值加上一个数，我们这个区间的区间和是不是加上了这个区间的长度乘上这个数？

我们要是给定了一个区间，那么我们把这个区间都加上一个值，要问这个区间的区间和，不就是原来的区间和+（长度*这个值）？

这样做是不是有点漏洞？如果我们把这个区间进行一次区间加操作，我们只加了这个区间的区间和，那要问在这之中的子区间呢？

我们一开始下面的区间和是不是并没有加上？（你没有把数列上的数加上诶），那么询问小区间是不是就错了呢？

管他那么多？我就是懒，不干。查到我下边的节点，我再更新下面的节点，查不到我干了又有什么用？

~~（你哪次作业不是那么干的）~~

就像这样，我们没有对这个区间进行下次的修改和查询，我们就不去继续修改这个节点的子节点了，我们给他上个标记就好了，这就是懒标记。很多人对这个东西叫法不一样，总之就是为了可以偷懒的标记，我习惯把维护这个数的数组叫做col（color），就是染色。

我们打完标记了就不管了？

不是的 ~~你敢不写完作业试试~~

我们当要查询到这个区间的时候，就把这个节点加上长度×这个标记的值（因为你要用了，不能再拖了），我们这个节点的子节点并没有更新，我们就给子节点打上标记，表示询问到这个区间的时候（查作业的时候）记得再加上这个值（按时抄写完作业）。这样就可以省不少时间（来玩NOI这款游戏）。

如何实现？

首先是区间修改。我们也可以像区间查询一样把要修改的区间变成线段树上有的节点，然后进行修改。

就是就修改每个节点的时候，先把自己的值加上，再把子节点打上标记

我们就先从染色（打标记）开刀入手

inline void color(int l,int r,int rt,int v){
    z[rt]=z[rt]+(r-l+1)*v;//区间长×要加的值（你这是区间和，一定记得要把区间长乘上）
    col[rt]+=v;//标记（这个地方用了加法，为什么？）
}

上面我们下传标记时是用的加，为什么？

我们如果十分恰好有两个标记都被记到了这个节点（物理作业和化学作业），你总不能只加一个吧（你只写物理作业化学老师能饶得过你？）。所以你要一起加起来。

下面是下传标记：

inline void push_col(int l,int r,int rt){
    if(col[rt]!=0){
        ll m=(l+r)>>1;//中点
        color(lson,col[rt]);//更新加下放标记
        color(rson,col[rt]);//
        col[rt]=0;//作业做完了就没了，别再做一遍了，记的清楚标记
    }
}

那么我们在修改的时候就和区间查询就十分相似：

inline void modify(int l,int r,int rt,int nowl,int nowr,int v){
    if(nowl<=l && r<=nowr){color(l,r,rt,v);return ;}//如果完全在这个区间内，就把这个区间染色
    ll m=(l+r)>>1;
    push_col(l,r,rt);//下传标记
    if(nowl<=m) modify(lson,nowl,nowr,v);//这里就是
    if(m<nowr)  modify(rson,nowl,nowr,v);//分治
    update(rt);//记得改完后要更新的哦
}

这里还要注意一点，我们之前的查询也要加上一句：

inline ll query(int l,int r,int rt,int nowl,int nowr){
    if(nowl<=l && r<=nowr){return z[rt];}
    push_col(l,r,rt);//也要标记下传的，因为和这个节点有关系了，不能让它还是错的
    ll m=(l+r)>>1;
    if(nowl<=m){
        if(m<nowr)
            return query(lson,nowl,nowr)+query(rson,nowl,nowr);
        else
            return query(lson,nowl,nowr);
    }else{
        return query(rson,nowl,nowr);
    }
}

具体用法：（代码）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#define go(i,j,n,k) for(register int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(register int i=j;i>=n;i-=k)
#define rep(i,x) for(register int i=h[x];i;i=e[i].next)
#define inf 1<<30
#define mn 100010
#define ll long long 
#define root 1,n,1 
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll z[mn*4],col[mn*4];
inline void update(int rt){
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
inline void color(int l,int r,int rt,ll v){
    z[rt]=z[rt]+(r-l+1)*v;
    col[rt]+=v;
}
inline void push_col(int l,int r,int rt){
    if(col[rt]!=0){
        int m=(l+r)>>1;
        color(lson,col[rt]);
        color(rson,col[rt]);
        col[rt]=0;
    }
}
inline void build(int l,int r,int rt){
    if(l==r){z[rt]=read(),col[rt]=0;return ;}
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    update(rt);
}
inline void modify(int l,int r,int rt,int nowl,int nowr,ll v){
    if(nowl<=l && r<=nowr){color(l,r,rt,v);return ;}
    int m=(l+r)>>1;
    push_col(l,r,rt);
    if(nowl<=m) modify(lson,nowl,nowr,v);
    if(m<nowr)  modify(rson,nowl,nowr,v);
    update(rt);
}
inline ll query(int l,int r,int rt,int nowl,int nowr){
    if(nowl<=l && r<=nowr){return z[rt];}
    int m=(l+r)>>1;
    push_col(l,r,rt);
    if(nowl<=m){
        if(m<nowr)
            return query(lson,nowl,nowr)+query(rson,nowl,nowr);
        else
            return query(lson,nowl,nowr);
    } else{
        return query(rson,nowl,nowr);
    }
}
int n,m;
int main(){
    n=read();
    m=read();
    build(root);
    go(i,1,m,1){
        int s=read();
        if(s==1){
            int x=read(),y=read(),k=read();
            modify(root,x,y,k);
        }else{
            int x=read(),y=read();
            cout<<query(root,x,y)<<"
";
        }
    }
    return 0;
}

实际上学到这里，线段树就基本讲完了。

我们如果想用线段树完美切题，要首先把线段树的代码（推荐是P3372）打熟，一遍一遍的打。因为如果你要用的话打错了很难debug，还是要多打板子。

二、线段树的时空使用

首先，我们建树是用了O(nlogn)的时间，要更新O(nlogn)个节点嘛

我们查询和修改实际上都是每次用了O(logn)级别的时间，如果有m个操作，就会有O(mlogn)时间复杂度。

比较重要的是线段树的空间。

我们写线段树的时候是按照二叉树的性质建树的，所以rt<<1就是左儿子，rt<<1|1就是右儿子。我们本来数列上是有n个节点，我们要用很多节点来维护，我们一个一个讨论其实就是n + n/2 + n/4 + n/8 + ··· + n/n个节点，所以我们至少要开2×n的数组。

而我的代码是开了mn<<2，也就是mn×4，这是为什么？

上个图好啦QwQ（丑图++）

我的节点编号是按照我们建树时的编号。

我们突然发现真的炸掉2×n了，有两个神一般的节点（30和31号）。

所以我们还是要开四倍的数组的。