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

### 本文章连载AC军团周报 ## -> 线段树 ： 从入门到入土【1】 #### 前言： 正如你所见，我这系列文章可以从入门来看，想入土的（伪）也可以进行观看（逃 本系列的文章将详讲线段树的思想，代码实现，并以一部分系列习题~~（这会不告诉你是哪一套，怕你直接关闭界面）~~来更深刻的了解线段树。 ### 一、线段树入门 很多人对于线段树的印象就是：代码长，de不出bug，容易写错，还是个高级数据结构~~吓人诶~~。 但如果真的讲起，就不是太难了。 大家还记得当年学的二叉树吗QwQ？ 大家还记得当年学的分治吗？ 对，线段树简单地说就是**用二叉树分治数列，来达到~~快速~~解决数列问题的目的**。（个人的理解方法） 线段树图：（来自网络QwQ）  这是一个很好看的图片，可惜这张图不形象，我上一张我自己画的图QwQ  虽说不好看，不过这张就比较直观的把分治的思想画出来了~~（强词夺理）~~。 我们拿个简单而又直观的例题理解一下吧： 经典线段树例题：我们给出一个长度为n的数列，对此数列有m次操作，有两种操作：第一个操作是对一个区间的数都加上v，第二个操作是求一个区间里所有数的和。 （大意：区间加，区间求和） 很多人看到区间求和，第一个想到的是：前缀和！！！ 可是我们怎么做到边修改边求和呢？单是前缀和怕是不行的呦。 我们先简化一下问题吧。 如何做到把单个点的值加v，求区间的和？ 我们不妨把一个数列上的数分为一个一个的线段（顾名思义，线段树嘛），如图分别是[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8]。我们可以直观的看出，我们相邻的两个区间的线段可以连接成一条线段，如：[1,1]和[2,2]可以合成[1,2]，那么我们加入要求[1,2]的区间和，那么不就是合成[1,2]这条线段的子线段[1,1],[2,2]这两条线段中数的和吗？ 那我们反过来想，我们如果把一个数列看作一条长线段[l,r]，那么我们可以把这个线段分为[1,mid],[mid+1,r]两条线段，简单的来想，我们要求[l,r]这条线段上的区间和，不就是[l,mid]的区间和加上[mid+1,r]的区间和吗？那么我们一层一层的分下去，直到分到线段长度都为1，那我们是不是可以直接读取这样的线段区间和（不就是数列上的单个数吗）。如果要问[1,4]的区间和，我们就可以分为[1,2]和[3,4]的区间和之和，进而分成[1,1]和[2,2]和[3,3]和[4,4]四个线段。如果我们这么分，把一个线段作为节点，一个线段的两个子线段作为儿子节点，那么我们一个数列所分出的线段可以像一棵二叉树，如果我们把这棵树上维护的是每个子线段的区间和，那么这棵树就叫做线段树。 我们的线段树就是维护的类似区间和的可以合并的区间性质。我们可以预处理（建树），将线段一层一层的分成一段段小区间，直到区间长为1，然后一层一层从小线段开始向上维护区间的性质（区间和），直到最顶端（数列本身长度）。 这就是我们所说的建树： **代码示例：** 首先是我这里的宏定义， #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 ```cpp inline void update(int rt){//更新节点信息，也就是合并左右儿子线段上的信息，这 //里是区间求和，那就把子线段上的和加起来 z[rt]=z[rt<<1]+z[rt<<1|1]; } inline void build(int l,int r,int rt){//l,r是我们所在树的节点的左右端点 //rt指这个节点的编号，这个编号也满 //足二叉树的性质，所以左儿子是 //rt<<1,右儿子是rt<<1|1(位运算 if(l==r){z[rt]=read();return ;} //分到了最短的线段，也就是长度为1的线段，也就是所 //在端点的数列对应的数 int m=(l+r)>>1; //找中点 build(lson); //递归实现分治 build(rson); update(rt); //更新节点的信息（合并左右儿子信息） } ``` 那我们查询一段区间和，直接读取部分区间和再合并就好啦！假如说我们要求区间[1,6]的区间和，我们可以把区间分为两个部分：在左边的（[1,4]）的部分，在右边（[5,8]）的部分，那我们询问的区间就分成了两部分：[1,4],[5,6]。然后我们看一看有没有可以直接读取的区间，我们这个例子就可以直接读取[1,4]（我们在线段树上维护了），这部分就是总区间中左半部分的和，那我们右半部分的和在[5,8]上，我们再去把[5,8]的这段区间按刚刚的操作分成[5,6],[7,8]两个区间，然后再去看有没有可以直接读取的区间。最后都读取完后把我们读取的和加起来就好了。 **听起来好麻烦诶** 不着急，我们先看看这部分的代码： ```cpp inline int query(int l,int r,int rt,int nowl,int nowr){ if(nowl<=l && r<=nowr){return z[rt];} //直接提取区间 int 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 inline void modify(int l,int r,int rt,int p,int v){ if(l==r){z[rt]+=v;return ;}//递归找到最底层要修改的叶节点并进行修改 int m=(l+r)>>1; if(p<=m) modify(lson,p,v);//向左进行寻找 else modify(rson,p,v);//向右进行寻找 update(rt);//回溯的时候就会重新更新一下这一部分的区间和 } ``` 那么我们简化的问题的完整代码就像这样了： ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> 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=next[i]) #define inf 1<<30 #define mn 500050 #define ll long long #define root 1,n,1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 inline int read(){ int 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; } int z[mn*4]; int n,m; inline void update(int rt){ z[rt]=z[rt<<1]+z[rt<<1|1]; } inline void build(int l,int r,int rt){ if(l==r){z[rt]=read();return ;} int m=(l+r)>>1; build(lson); build(rson); update(rt); } inline void modify(int l,int r,int rt,int p,int v){ if(l==r){z[rt]+=v;return ;} int m=(l+r)>>1; if(p<=m) modify(lson,p,v); else modify(rson,p,v); update(rt); } inline int query(int l,int r,int rt,int nowl,int nowr){ if(nowl<=l && r<=nowr){return z[rt];} int 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); } } int main(){ n=read(); m=read(); build(root); go(i,1,m,1){ int s=read(); if(s==1){ int x=read(),k=read(); modify(root,x,k); } else if(s==2){ int x=read(),y=read(); cout<<query(root,x,y)<<"\n"; } } return 0; } ``` ~~我不会告诉你这是P3374的代码~~ 这只是单点啊？ #### 回到我们的原问题：区间修改，区间查询 我们区间查询的问题已经解决了，但是我们只会单点修改，怎么办？ #### 我们作为思考题，想想线段树上维护的究竟是个啥，然后进行标记，思考如何进行区间查询（就不要想拿单点查询对每个数都进行一次操作了），我们下一期再对这个操作进行详细的讲解（因为这部分很重要，不细讲会出问题） ### 敬请期待下一期的 -> 线段树：从入门到入土【2】 ### 推荐习题： P3374 【模板】树状数组 别看是树状数组的问题，实际上线段树是很好解决的