题解 P3372 【【模板】线段树 1】

线段树在区间查询和区间修改上有两种操作，一是标记下传，二是标记永久化。前者许多神犇都发过了，我就捡个漏，发一篇标记永久化的题解。 顾名思义，两者的区别就是在处理标记时，前者把标记下传到两个儿子身上同时自己清零；而后者则一步处理好自己的标记。相对而言，标记永久化的代码更短，在树套树及可持久化数据结构中使用较为方便，但同时操作技巧要求更高，也不容易理解（我当初搞了两天），希望我的经验能对大家有所帮助qwq。 ---------------------------------- 先申明几个参数：k表示当前节点的序号，v表示要增加的数（根据题意，要用 long long），l 和 r 表示当前节点所管辖的区间，x 和 y 表示要修改或询问的区间的区间，其他参数都是通用的那个意思了。 重点讲修改和查询的两个函数，讲解的模式是先放整个函数的代码块，然后是某一步的代码块及其讲解。某一步的讲解也可能在下文有进一步补充。 本人讲解难免不清，建议读者边看边画图加深理解。 ### 修改函数modify( ) ```cpp void modify(int k,ll v,int l,int r,int x,int y) { if(x<=l&&r<=y) { add[k]+=v; return; } sum[k]+=(min(r,y)-max(l,x)+1)*v; int mid=(l+r)/2; if(x<=mid) modify(k*2,v,l,mid,x,y); if(mid<y) modify(k*2+1,v,mid+1,r,x,y); } ``` ##### 递归边界： ```cpp if(x<=l&&r<=y) { add[k]+=v; return; } ``` 试想，如果当前的区间被要修改的区间所覆盖，就意味着当前区间内所有的子节点都要修改，就没必要继续递归下去（这就是线段树的优势），直接打上标记行了，而sum值不需要改动（此操作在下文有照应）。 ##### sum值修改 ```cpp sum[k]+=(min(r,y)-max(l,x)+1)*v; ``` 线段树每个节点所管辖的区间是通过二分来分配的，但实际上要修改的区间往往是由某些区间的全部和另外一些区间的一部分组成的。 这就意味着有一些区间是只有一部分要修改，这种情况时，就不能直接修改add标记了，（因为标记本身无法记录具体作用在哪个部分上） 只好直接修改sum值。 那么这一部分是怎么计算得来的呢？我们一右端点为例，分类讨论。 1、如果当前区间的右端点（r）在修改区间的右端点（y）的左边（即r<y），显然当前区间的右端点内（即右端点往左）的都要改，以外（即往右）的它管不着。所以要处理的区间的右端点为r； 2、反之，修改区间的右端点（y）在当前区间的右端点（r）的左边（即y<=r），则修改区间的右端点内的区间显然都要加上v，则修改区间的右端点外的区间虽说当前节点管得着，但并不要求这部分修改。所以要处理的区间右端点为y； 综上，就有了min ( r , y ) 。 左端点同理。 ##### 递归条件。 ```cpp int mid=(l+r)/2; if(x<=mid) modify(k*2,v,l,mid,x,y); if(mid<y) modify(k*2+1,v,mid+1,r,x,y); ``` 这步比较好理解，如果要修改的区间与当前节点的左儿子有交集（即 x <= mid ），才递归左儿子，右儿子同理。 ### 查询函数query( ) 形式上和modify函数很像。 ```cpp ll query(int k,int l,int r,int x,int y) { if(x<=l&&r<=y) return sum[k]+(r-l+1)*add[k]; ll res=(min(r,y)-max(l,x)+1)*add[k]; int mid=(l+r)/2; if(x<=mid) res+=query(k*2,l,mid,x,y); if(mid<y) res+=query(k*2+1,mid+1,r,x,y); return res; } ``` ##### 返回值res的处理 1 应该会有读者感到奇怪（包括当年的我），为什么又要加add值，又要加sum值，会不会有重复的呢？但只要理解了modify函数，就很简单了。 当前区间，有可能只被修改了一部分，有可能只试过整个区间被修改，也可能同时都有或都没有。我们不妨分类讨论。 1、若只被修改过一部分，那么sum值已经把要修改的部分加上了，而因为不曾试过整个区间被修改，所以其add值为0，加上也无妨。 所以返回sum+add； 2、若只试过整个区间被修改，那么sum值不曾被修改过，标记都打到add上了。 所以返回sum+add； 3、若两者都曾试过，sum值负责加上“一部分”的那些，add值负责加上“整个区间”的那些 。 所以两个都要加上，返回sum+add； 4、若都没试过··· 结合以上几点感性易证，应返回sum+add。 综上，把sum和add都加上就对了。 另外，对于sum值，由于它针对的是整个区间，无法分割，这既导致了它不能立刻加上，但也使得它在递归达到边界时最终一定会被补上。 然后再对每一步补充一下。 ##### 递归边界。 ```cpp if(x<=l&&r<=y) return sum[k]+(r-l+1)*add[k]; ``` 很简单，既然当前区间都被查询区间给覆盖了，那肯定sum和add都要加上啦~ ```cpp ll res=(min(r,y)-max(l,x)+1)*add[k]; ``` ##### 返回值res的处理 2 此处为什么只加add值呢？那是因为当前节点并没有被查询区间给完全覆盖，为什么要加add值和add值针对的区间即(min(r,y)-max(l,x)+1)的由来前文已提。至于sum值，由于它针对的是整个区间，无法分割，这既导致了它不能立刻加上，但也使得它在递归时最终一定会被补上。 当然res还要加上两个儿子的（如果满足递归条件的话）。 至于递归条件与前文相同，此处便不再赘述。 --------------------- 终于——完整的AC代码来了，一些细节也会在里面补充。 ```cpp #include<cstdio> #include<iostream> #define ll long long using namespace std; const int M=100005; int n,m; ll a[M],sum[M*4],add[M*4]; //别忘了，线段树要开4倍大小的数组 //根据题意，要用long long ,被坑了好几次 void build(int k,int l,int r)//建树，很简单 { if(l==r) { sum[k]=a[l]; //我曾手残sum[k]=l >_< return; } int mid=(l+r)/2; //这些地方可以用位运算优化 build(k*2,l,mid); build(k*2+1,mid+1,r); sum[k]=sum[k*2+1]+sum[k*2]; return; } void modify(int k,ll v,int l,int r,int x,int y) { if(x<=l&&r<=y) { add[k]+=v; return; } sum[k]+=(min(r,y)-max(l,x)+1)*v; int mid=(l+r)/2; if(x<=mid) modify(k*2,v,l,mid,x,y); if(mid<y) modify(k*2+1,v,mid+1,r,x,y); } ll query(int k,int l,int r,int x,int y) { if(x<=l&&r<=y) return sum[k]+(r-l+1)*add[k]; //我曾又手残sum[k]+(r-l+1)*a[k] >_< ll res=(min(r,y)-max(l,x)+1)*add[k]; int mid=(l+r)/2; if(x<=mid) res+=query(k*2,l,mid,x,y); if(mid<y) res+=query(k*2+1,mid+1,r,x,y); return res; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); for(int i=1,x,y;i<=m;i++) { scanf("%d",&x); if(x==1) { ll z; //此处也要long long scanf("%d%d%lld",&x,&y,&z);//读入时要long long >_< modify(1,z,1,n,x,y); } else { scanf("%d%d",&x,&y); printf("%lld\n",query(1,1,n,x,y));//输出是也要long long >_< } } return 0; } ``` ------------ 当然，你可能无法马上理解，但你可以再看几次，再画几个图，或者隔几天再想。无论是为了线段树的强大功能，还是陶醉于信息学本身的魅力，我都衷心地祝愿每一个读者能理解标记永久化的写法。 最后，本人来发表一下感言qwq。 1. 感谢洛谷提供的好平台； 2. 感谢管理员大大的辛勤付出； 3. 感谢信息学奥赛一本通·提高篇的详细讲解 ~~其实不怎么详细~~； 4. 感谢自己~~入坑~~学信竞以来不懈的努力； 5. 感谢随手留赞的你。