洛谷P3372线段树1

难以平复鸡冻的心情，虽然可能在大佬眼里这是水题，但对蒟蒻的我来说这是个巨大的突破（谢谢我最亲爱的lp陪我写完，给我力量）。网上关于线段树的题解都很玄学，包括李煜东的《算法竞赛进阶指南》中的相关内容一样，不能给我一眼看上去就明白的清晰的思路。请允许我作为用了10个小时做出这道题的“过来人”清晰的提一下比较难想的几个点。首先我根据书上和其它博客上的大致思路，选择了结构体来实现，其实用数组也是可以的，但我感觉更加的清晰。

第一个难点，书上的图给的样例就是1....n。我们的结点表示的区间同样也是类似的，那么我这样的蒟蒻就会产生误解，其实就是根据读入的编号，这点是如何发现的呢？我们可以根据洛谷上面的题面知道，对连续区间的修改，不难想到表示的区间就是读入时的编号。

第二个难点，如何建树，这个书上给的解释很清楚，按照书上的来就不会有问题。但是有的博客上的和书上不一样，它没有用下文的shu[x].l，shu[x].r来表示对应的x结点所代表的区间，其实这也是可以的，起码对于我的程序来说，因为你寻找区间的时候用的递归是可以承载这个信息的。

第三个难点，如何给区间中的每一个数加值，只要明白了这一点，其实后面的寻找区间中的和也就是我的find_tree和add_tree中的操作过程是大致相同的。关键是看边界条件，我会在代码上标注出来。

第四个难点，也就是懒惰标记，这是线段树优点的关键所在，就是记录下在何时你的区间正好可以加（范围只能小，不能超），关键看操作。

ps：洛谷中的运势是大吉，诸事皆宜，看起来有几分道理。

 #include<bits/stdc++.h>

 using namespace std;

 struct node{

     long long l,r,dat;

 }shu[];//结构体，l代表区间最左，r代表区间最右，dat是区间中数的和。

 long long a[];//读入和后面建树要用

 long long lazy[];//懒惰标记

 long long b,c,d,ans;

 void build_tree(long long x,long long y,long long z){//建树

     shu[x].l=y;shu[x].r=z;

     if (y==z) {shu[x].dat=a[y];return;}//如果区间大小是1则代表是叶结点，不用再向下建树

     else {

         long long m=(z+y) >> ;//中点

         build_tree(x*,y,m);//最子树的结点是2*x（根据完全二叉树来做的，这个就是用数组模拟，说建数就是装逼的说法，本质相同，只是在你的思维里代表了另一种结构。）

         build_tree(x*+,m+,z);

         shu[x].dat=shu[x*].dat+shu[x*+].dat;//区间和等于左子区间和+右子区间和。

     }

 }

 void add_tree(long long x,long long add){//区间加值

     shu[x].dat+=add;//加上区间中要加的值

     if (b<=shu[x].l&&shu[x].r<=c) {//如果区间在要加的区间之中就用懒惰标记记录它的子区间，因为它已经被加了

         if (shu[x].l!=shu[x].r){

             lazy[x*]+=d;

             lazy[x*+]+=d;

         }

         return;

     }

     else {

         long long mid=(shu[x].l+shu[x].r)/;//4个边界的判断，读者可以自己去想一下，是本题的难点。

         if (mid>=b&&mid<=c) {

             if (shu[x].l>=b) add_tree(x*,(mid-shu[x].l+)*d);

             else add_tree(x*,(mid-b+)*d);

         }

         if (mid+<=c&&mid+>=b) {

             if (shu[x].r>=c) add_tree(x*+,(c-mid)*d);

             else add_tree(x*+,(shu[x].r-mid)*d);//我是用add这个局部变量来表示要加的值，用此区间中有多少是包括在要加区间中的再*加的数

         }

         if (mid>c){

             if (shu[x].l>=b&&shu[x].l<=c) add_tree(x*,(c-shu[x].l+)*d);

             else if (shu[x].l<b)add_tree(x*,(c-b+)*d);

         }

         if (mid+<b){

             if (shu[x].r<=c&&shu[x].r>=b) add_tree(x*+,(shu[x].r-b+)*d);

             else if (shu[x].r>c) add_tree(x*+,(c-b+)*d);

         }

     }

 }


 void find_tree(long long x){//查找区间和，和上面一个过程十分的相似。

     shu[x].dat+=(lazy[x]*(shu[x].r-shu[x].l+));

     if (b<=shu[x].l&&c>=shu[x].r){

         ans=ans+shu[x].dat;

         if (lazy[x]!=&&shu[x].l!=shu[x].r){

             lazy[x*]+=lazy[x];

             lazy[x*+]+=lazy[x];

             lazy[x]=;

         }

         if (shu[x].r==shu[x].l) lazy[x]=;

         return;

     }

     else {

         if (shu[x].r==shu[x].l) {lazy[x]=;return;}

         long long mid=(shu[x].l+shu[x].r)/;

         if (lazy[x]!=){

             lazy[x*]+=lazy[x];

             lazy[x*+]+=lazy[x];

             lazy[x]=;

         }

         if (mid>=b&&mid<=c) find_tree(x*);

         if ((mid+)<=c&&(mid+)>=b) find_tree((x*)+);

         if (mid>c&&shu[x].l<=c) find_tree(x*);

         if (mid+<b&&shu[x].r>=b) find_tree(x*+);

     }

 }


 int main(){

     long long n,m;

     cin>>n>>m;//读入

     memset(lazy,,sizeof(lazy));

     for (long long i=;i<=n;i++) cin>>a[i];

     build_tree(,,n);//建树

     for (long long i=;i<=m;i++){

         long long a;

         cin>>a;

         if (a==){

             cin>>b>>c>>d;

             add_tree(,(c-b+)*d);//加值

         }

         else {

             ans=;

             cin>>b>>c;

             find_tree();

             cout<<ans<<endl;//查询

         }

     }

 }

再次用了标准的模板格式进行了标准化的修改。下面是代码。

 #include<bits/stdc++.h>

 using namespace std;

 struct node{

     long long l,r,dat;

 }shu[];

 long long lazy[];

 long long a[];

 long long ans,b,c,d,n,m;

 void build_tree(long long x,long long y,long long z){

     shu[x].l=y;shu[x].r=z;

     if (y==z){

         shu[x].dat=a[y];

         return;

     }

     long long mid=(y+z)/;

     build_tree(x*,y,mid);

     build_tree(x*+,mid+,z);

     shu[x].dat=shu[x*].dat+shu[x*+].dat;

 }

 void add_tree(long long x){

     if (shu[x].l>=b&&shu[x].r<=c){

         shu[x].dat+=(d*(shu[x].r-shu[x].l+));

         if (shu[x].l!=shu[x].r){

             lazy[x*]+=d;

             lazy[x*+]+=d;

         }

         return;

     }

     long long mid=(shu[x].l+shu[x].r)/;

     if (b<=mid) add_tree(*x);

     if (c>mid) add_tree(*x+);

     shu[x].dat=shu[x*].dat+shu[x*+].dat+lazy[*x]*(shu[x*].r-shu[x*].l+)+lazy[*x+]*(shu[x*+].r-shu[x*+].l+);

 }

 void find_tree(long long x){

     if (lazy[x]!=)shu[x].dat+=lazy[x]*(shu[x].r-shu[x].l+);

     if (shu[x].l!=shu[x].r){

         lazy[x*]+=lazy[x];

         lazy[x*+]+=lazy[x];

     }

     lazy[x]=;

     if (shu[x].l>=b&&shu[x].r<=c){

         ans+=shu[x].dat;

         return;

     }

     long long mid=(shu[x].l+shu[x].r)/;

     if (b<=mid) find_tree(*x);

     if (c>mid) find_tree(*x+);

 }

 int main(){

     cin>>n>>m;

     for (long long i=;i<=n;i++) cin>>a[i];

     build_tree(,,n);

     memset(lazy,,sizeof(lazy));

     for (long long i=;i<=m;i++){

         long long a;

         cin>>a;

         if (a==){

             cin>>b>>c>>d;

             add_tree();

         }

         else if (a==){

             cin>>b>>c;

             ans=;

             find_tree();

             cout<<ans<<endl;

         }

     }

 }

可以看出来，更加的简洁了。（书上的解法真标准）但是思路和我之前的程序是大相径庭的，可以仔细研究一下两者的区别。

巴特西

洛谷P3372线段树1

最新文章

热门文章