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

### 本文章连载AC军团周报 ## -> 线段树 ： 从入门到入土【2】 ### 前言： 第二期了，我们要把上一期留下的锅补一下。 这一期的内容主要是懒标记，处理区间修改的问题。 我们最后再分析一下线段树时间复杂度 ### 一、线段树入门（续） 我们上一期学习了线段树的入门操作，主要是进行建树，区间查询，单点修改。我们来仔细回想一下吧。 ……………………回想时间…………………… 如果你回想完了，就再思考一下上一节留下的问题： **如何做到区间修改** 我们考虑时间复杂度的话一个一个进行单点修改是肯定不行的（之后我们会分析时间复杂度），你也不能一个一个加。 我们考虑我们线段树维护的是什么 是不是线段上的区间和？ 假如我们给一个区间中的每个值加上一个数，我们这个区间的区间和是不是加上了这个区间的长度乘上这个数？ 我们要是给定了一个区间，那么我们把这个区间都加上一个值，要问这个区间的区间和，不就是原来的区间和+（长度*这个值）？ 这样做是不是有点漏洞？如果我们把这个区间进行一次区间加操作，我们只加了这个区间的区间和，那要问在这之中的子区间呢？ 我们一开始下面的区间和是不是并没有加上？（你没有把数列上的数加上诶），那么询问小区间是不是就错了呢？ 管他那么多？**我就是懒**，不干。查到我下边的节点，我再更新下面的节点，查不到我干了又有什么用？ **~~（你哪次作业不是那么干的）~~** 就像这样，我们没有对这个区间进行下次的修改和查询，我们就不去继续修改这个节点的子节点了，我们给他上个标记就好了，这就是**懒标记**。很多人对这个东西叫法不一样，总之就是为了可以偷懒的标记，我习惯把维护这个数的数组叫做col（color），就是染色。 我们打完标记了就不管了？ 不是的 **~~你敢不写完作业试试~~** 我们当要查询到这个区间的时候，就把这个节点加上长度×这个标记的值（因为你要用了，不能再拖了），我们这个节点的子节点并没有更新，我们就给子节点打上标记，表示询问到这个区间的时候（查作业的时候）记得再加上这个值（按时~~抄~~写完作业）。这样就可以省不少时间（来玩NOI这款游戏）。 如何实现？ 首先是区间修改。我们也可以像区间查询一样把要修改的区间变成线段树上有的节点，然后进行修改。 就是就修改每个节点的时候，先把自己的值加上，再把子节点打上标记 我们就先从染色（打标记）~~开刀~~入手 ```cpp inline void color(int l,int r,int rt,int v){ z[rt]=z[rt]+(r-l+1)*v;//区间长×要加的值（你这是区间和，一定记得要把区间长乘上） col[rt]+=v;//标记（这个地方用了加法，为什么？） } ``` 上面我们下传标记时是用的加，为什么？ 我们如果十分恰好有两个标记都被记到了这个节点（物理作业和化学作业），你总不能只加一个吧（你只写物理作业化学老师能饶得过你？）。所以你要一起加起来。 下面是下传标记： ```cpp 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;//作业做完了就没了，别再做一遍了，记的清楚标记 } } ``` 那么我们在修改的时候就和区间查询就十分相似： ```cpp 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);//记得改完后要更新的哦 } ``` 这里还要注意一点，我们之前的查询也要加上一句： ```cpp 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); } } ``` ### 具体用法：（代码） ```cpp #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)<<"\n"; } } 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号）。 所以我们还是要开四倍的数组的。 ### 对于线段树的应用我们下期继续讲解。 #### 推荐习题： P3372 【模板】线段树 1 P3373 【模板】线段树 2 P1276 校门外的树（加强版） //为什么不用线段树试试 P1886 滑动窗口 //明明标了线段树为什么不用 P4779 【模板】单源最短路径（标准版）//什么鬼？ //线段树是可以优化Dijkstra的 ##### 这几个习题是下期的部分内容（线段树的应用）