难以平复鸡冻的心情，虽然可能在大佬眼里这是水题，但对蒟蒻的我来说这是个巨大的突破（谢谢我最亲爱的lp陪我写完，给我力量）。网上关于线段树的题解都很玄学，包括李煜东的《算法竞赛进阶指南》中的相关内容一样，不能给我一眼看上去就明白的清晰的思路。请允许我作为用了10个小时做出这道题的“过来人”清晰的提一下比较难想的几个点。首先我根据书上和其它博客上的大致思路，选择了结构体来实现，其实用数组也是可以的，但我感觉更加的清晰。
第一个难点，书上的图给的样例就是1....n。我们的结点表示的区间同样也是类似的，那么我这样的蒟蒻就会产生误解，其实就是根据读入的编号，这点是如何发现的呢？我们可以根据洛谷上面的题面知道，对连续区间的修改，不难想到表示的区间就是读入时的编号。
第二个难点，如何建树，这个书上给的解释很清楚，按照书上的来就不会有问题。但是有的博客上的和书上不一样，它没有用下文的shu[x].l，shu[x].r来表示对应的x结点所代表的区间，其实这也是可以的，起码对于我的程序来说，因为你寻找区间的时候用的递归是可以承载这个信息的。
第三个难点，如何给区间中的每一个数加值，只要明白了这一点，其实后面的寻找区间中的和也就是我的find_tree和add_tree中的操作过程是大致相同的。关键是看边界条件，我会在代码上标注出来。
第四个难点，也就是懒惰标记，这是线段树优点的关键所在，就是记录下在何时你的区间正好可以加（范围只能小，不能超），关键看操作。
ps：洛谷中的运势是大吉，诸事皆宜，看起来有几分道理。
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 long long l,r,dat; 5 }shu[400010];//结构体，l代表区间最左，r代表区间最右，dat是区间中数的和。 6 long long a[100010];//读入和后面建树要用 7 long long lazy[400010];//懒惰标记 8 long long b,c,d,ans;
9 void build_tree(long long x,long long y,long long z){//建树 10 shu[x].l=y;shu[x].r=z; 11 if (y==z) {shu[x].dat=a[y];return;}//如果区间大小是1则代表是叶结点，不用再向下建树 12 else { 13 long long m=(z+y) >> 1;//中点 14 build_tree(x*2,y,m);//最子树的结点是2*x（根据完全二叉树来做的，这个就是用数组模拟，说建数就是装逼的说法，本质相同，只是在你的思维里代表了另一种结构。） 15 build_tree(x*2+1,m+1,z); 16 shu[x].dat=shu[x*2].dat+shu[x*2+1].dat;//区间和等于左子区间和+右子区间和。 17 } 18 }
19 void add_tree(long long x,long long add){//区间加值 20 shu[x].dat+=add;//加上区间中要加的值 21 if (b<=shu[x].l&&shu[x].r<=c) {//如果区间在要加的区间之中就用懒惰标记记录它的子区间，因为它已经被加了 22 if (shu[x].l!=shu[x].r){ 23 lazy[x*2]+=d; 24 lazy[x*2+1]+=d; 25 } 26 return; 27 } 28 else { 29 long long mid=(shu[x].l+shu[x].r)/2;//4个边界的判断，读者可以自己去想一下，是本题的难点。 30 if (mid>=b&&mid<=c) { 31 if (shu[x].l>=b) add_tree(x*2,(mid-shu[x].l+1)*d); 32 else add_tree(x*2,(mid-b+1)*d); 33 } 34 if (mid+1<=c&&mid+1>=b) { 35 if (shu[x].r>=c) add_tree(x*2+1,(c-mid)*d); 36 else add_tree(x*2+1,(shu[x].r-mid)*d);//我是用add这个局部变量来表示要加的值，用此区间中有多少是包括在要加区间中的再*加的数 37 } 38 if (mid>c){ 39 if (shu[x].l>=b&&shu[x].l<=c) add_tree(x*2,(c-shu[x].l+1)*d); 40 else if (shu[x].l<b)add_tree(x*2,(c-b+1)*d); 41 } 42 if (mid+1<b){ 43 if (shu[x].r<=c&&shu[x].r>=b) add_tree(x*2+1,(shu[x].r-b+1)*d); 44 else if (shu[x].r>c) add_tree(x*2+1,(c-b+1)*d); 45 } 46 } 47 }
48 void find_tree(long long x){//查找区间和，和上面一个过程十分的相似。 49 shu[x].dat+=(lazy[x]*(shu[x].r-shu[x].l+1)); 50 if (b<=shu[x].l&&c>=shu[x].r){ 51 ans=ans+shu[x].dat; 52 if (lazy[x]!=0&&shu[x].l!=shu[x].r){ 53 lazy[x*2]+=lazy[x]; 54 lazy[x*2+1]+=lazy[x]; 55 lazy[x]=0; 56 } 57 if (shu[x].r==shu[x].l) lazy[x]=0; 58 return; 59 } 60 else { 61 if (shu[x].r==shu[x].l) {lazy[x]=0;return;} 62 long long mid=(shu[x].l+shu[x].r)/2; 63 if (lazy[x]!=0){ 64 lazy[x*2]+=lazy[x]; 65 lazy[x*2+1]+=lazy[x]; 66 lazy[x]=0; 67 } 68 if (mid>=b&&mid<=c) find_tree(x*2); 69 if ((mid+1)<=c&&(mid+1)>=b) find_tree((x*2)+1); 70 if (mid>c&&shu[x].l<=c) find_tree(x*2); 71 if (mid+1<b&&shu[x].r>=b) find_tree(x*2+1); 72 } 73 }
74 int main(){ 75 long long n,m; 76 cin>>n>>m;//读入 77 memset(lazy,0,sizeof(lazy)); 78 for (long long i=1;i<=n;i++) cin>>a[i]; 79 build_tree(1,1,n);//建树 80 for (long long i=1;i<=m;i++){ 81 long long a; 82 cin>>a; 83 if (a==1){ 84 cin>>b>>c>>d; 85 add_tree(1,(c-b+1)*d);//加值 86 } 87 else { 88 ans=0; 89 cin>>b>>c; 90 find_tree(1); 91 cout<<ans<<endl;//查询 92 } 93 } 94 }
再次用了标准的模板格式进行了标准化的修改。下面是代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 long long l,r,dat; 5 }shu[400010]; 6 long long lazy[400010]; 7 long long a[100010]; 8 long long ans,b,c,d,n,m; 9 void build_tree(long long x,long long y,long long z){ 10 shu[x].l=y;shu[x].r=z; 11 if (y==z){ 12 shu[x].dat=a[y]; 13 return; 14 } 15 long long mid=(y+z)/2; 16 build_tree(x*2,y,mid); 17 build_tree(x*2+1,mid+1,z); 18 shu[x].dat=shu[x*2].dat+shu[x*2+1].dat; 19 } 20 void add_tree(long long x){ 21 if (shu[x].l>=b&&shu[x].r<=c){ 22 shu[x].dat+=(d*(shu[x].r-shu[x].l+1)); 23 if (shu[x].l!=shu[x].r){ 24 lazy[x*2]+=d; 25 lazy[x*2+1]+=d; 26 } 27 return; 28 } 29 long long mid=(shu[x].l+shu[x].r)/2; 30 if (b<=mid) add_tree(2*x); 31 if (c>mid) add_tree(2*x+1); 32 shu[x].dat=shu[x*2].dat+shu[x*2+1].dat+lazy[2*x]*(shu[x*2].r-shu[x*2].l+1)+lazy[2*x+1]*(shu[x*2+1].r-shu[x*2+1].l+1); 33 } 34 void find_tree(long long x){ 35 if (lazy[x]!=0)shu[x].dat+=lazy[x]*(shu[x].r-shu[x].l+1); 36 if (shu[x].l!=shu[x].r){ 37 lazy[x*2]+=lazy[x]; 38 lazy[x*2+1]+=lazy[x]; 39 } 40 lazy[x]=0; 41 if (shu[x].l>=b&&shu[x].r<=c){ 42 ans+=shu[x].dat; 43 return; 44 } 45 long long mid=(shu[x].l+shu[x].r)/2; 46 if (b<=mid) find_tree(2*x); 47 if (c>mid) find_tree(2*x+1); 48 } 49 int main(){ 50 cin>>n>>m; 51 for (long long i=1;i<=n;i++) cin>>a[i]; 52 build_tree(1,1,n); 53 memset(lazy,0,sizeof(lazy)); 54 for (long long i=1;i<=m;i++){ 55 long long a; 56 cin>>a; 57 if (a==1){ 58 cin>>b>>c>>d; 59 add_tree(1); 60 } 61 else if (a==2){ 62 cin>>b>>c; 63 ans=0; 64 find_tree(1); 65 cout<<ans<<endl; 66 } 67 } 68 }
可以看出来，更加的简洁了。（书上的解法真标准）但是思路和我之前的程序是大相径庭的，可以仔细研究一下两者的区别。