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

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

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

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

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

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

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

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

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

如何做到区间修改

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

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

是不是线段上的区间和？

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

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

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

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

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

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

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

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

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

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

如何实现？

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

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

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

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

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

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

下面是下传标记：

inline void push_col(int l,int r,int rt){if(col[rt]!=0){ll m=(lr)>>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=(lr)>>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=(lr)>>1;if(nowl<=m){if(m<nowr)return query(lson,nowl,nowr)query(rson,nowl,nowr);elsereturn 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<<0
#define mn 100010
#define ll long long 
#define root 1,n,1 
#define lson l,m,rt<<1
#define rson m1,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*10ch-	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-l1)*v;col[rt]=v;
}
inline void push_col(int l,int r,int rt){if(col[rt]!=0){int m=(lr)>>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=(lr)>>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=(lr)>>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=(lr)>>1;push_col(l,r,rt);if(nowl<=m){if(m<nowr)return query(lson,nowl,nowr)query(rson,nowl,nowr);elsereturn 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)<<\n;}}return 0;
}

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

我们如果想用线段树完美切题，要首先把线段树的代码（推荐是P72）打熟，一遍一遍的打。因为如果你要用的话打错了很难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了，有两个神一般的节点（0和1号）。

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

推荐习题：

P72 【模板】线段树 1
P7 【模板】线段树 2
P1276 校门外的树（加强版） //为什么不用线段树试试
P1886 滑动窗口 //明明标了线段树为什么不用
P4779 【模板】单源最短路径（标准版）//什么鬼？
//线段树是可以优化Dijkstra的

这几个习题是下期的部分内容（线段树的应用）

转载于:.html