线段树（标记版）

第一种操作

        与上一题不同的是，本题要求某区间内的每一个数都要加上y。为了达到这个目的，我们需要额外维护一个v数组。v[i] = k表示编号为i的节点对应的区间内的每个点要加上k。此时f数组的含义也会相应地发生变化，f[i] = k表示编号为i的节点对应的区间在不考虑v数组的影响下的和（注意，f数组只是排除了该区间之上区间的v的影响，并不意味着f数组存储的就是最初放入数列中的对应元素和，因为该区间下面也会有v数组的影响）。我们可以看到，v数组对应的实际上是“父树”（包括自身），因为“父树”总是包含当前区间；f数组对应的是“子树”（不包括自身），因为所有子树的并就是父树。如图——

第二种操作

        当我们要计算真正的某段区间内元素的和时，我们只需要合并考虑v数组和f数组的影响即可。由于该区间往上的区间都包含该区间，所以在考虑该区间的v数组影响时，我们要把前面的v值都累加起来，为此引进记录v值和的变量p。

#include
using namespace std;
const int N = 400010;
int n;
int m;
long long f[N];
long long v[N];
long long root[N];
void buildtree(int k,int l,int r)
{if(l==r){f[k] = root[l];return;}int m = (l+r)>>1;buildtree(k+k,l,m);buildtree(k+k+1,m+1,r);f[k] = f[k+k]+f[k+k+1];
}
//这句话意为在编号k代表的区间【l,r】内的【x,y】区间内的每个数都要加上z
void Insert(int k,int l,int r,int x,int y,long long z)
{if(l==x&&r==y){//此时要操作的区间就是【l,r】，那么根据v数组的含义，编号k代表的区间（就是【l,r】就要每个数加上z）v[k]+=z;return;}//由于【x,y】包含于【l,r】，且长度为（y-x+1）那么在不考虑v数组的影响下，节点k代表的区间就要加上（y-x+1）*zf[k] += (y-x+1)*z;int m = (l+r)>>1;//类上题，递归地插入if(y<=m)    Insert(k+k,l,m,x,y,z);else if(x>=m+1) Insert(k+k+1,m+1,r,x,y,z);else    Insert(k+k,l,m,x,m,z),Insert(k+k+1,m+1,r,m+1,y,z);
}
long long calculate(int k,int l,int r,int x,int y,long long p)
{//p记录的是当前节点往上的路径上的点的v的和，那么加上这一层的v后就变成包括这一层的往上的路径上的点的v的和p+=v[k];if(l==x&&r==y)//上下两部分的和加起来return p*(y-x+1)+f[k];int m = (l+r)>>1;//类似第，递归计算左子树的和与右子树的和if(y<=m)    return calculate(k+k,l,m,x,y,p);else if(x>=m+1) return calculate(k+k+1,m+1,r,x,y,p);else    return calculate(k+k,l,m,x,m,p)+calculate(k+k+1,m+1,r,m+1,y,p);
}
int main()
{scanf("%d%d",&n,&m);for(int i = 1;i<=n;i++) scanf("%d",&root[i]);buildtree(1,1,n);while(m--){int t;scanf("%d",&t);if(t==1){int x,y;//别忘了k要以long long形式读入！long long k;scanf("%d%d%lld",&x,&y,&k);Insert(1,1,n,x,y,k);}else{int x,y;scanf("%d%d",&x,&y);//注意输出格式！别忘了换行！printf("%lld\n",calculate(1,1,n,x,y,0));}}return 0;

线段树（下放标记版）

        在上一个版本的基础上我们能否再进行改进呢？如果我们不引入记录v值和的p变量，就要设法将前面的v值置为0。为此我们这样考虑：假若某父节点的v值增加了k，不就相当于它的两个子节点的v值都增加v么？这是因为，两个子节点的并恰好就是父节点呀！这样一来，我们就执行了一个标记“层层下放”的操作，直到当前要查询的区间，它的v值就是前面的累加了。但是这样的“下放”会带来一个问题，即f数组的数据变得混乱。为了修正f数组，我们可以考虑f数组是怎么生成的？它表示的是不考虑该区间以上区间v数组影响的情况下该区间的元素和。换句话说，f数组的值只与该区间以下的f值好v值有关。因此我们实际上可以将区间按照左右子树写出这样的关系式：f[k] = f[k+k]+v[k+k](m-l+1)+f[k+k+1]+v[k+k+1](r-m)，这里m表示区间【l,r】的中点，即m = (l+r)>>1。

#include
using namespace std;
const int M = 400010,N = 100010;
//真服了，以后干脆什么都开long long得了
long long f[M],root[N],v[M],n,m;
void buildtree(int k,int l,int r)
{if(l==r){f[k] = root[l];return;}int m = (l+r)/2;buildtree(k+k,l,m);buildtree(k+k+1,m+1,r);f[k] = f[k+k]+f[k+k+1];
}
void Insert(int k,int l,int r,int x,int y,long long z)
{if(l==x&&r==y) {v[k]+=z;return;}//如果某点v值不为0，我们就“下放”，让它的两个子节点的v值增加等价于if(v[k]){v[k+k]+=v[k];v[k+k+1]+=v[k];v[k] = 0;}int m = (l+r)/2;if(y<=m)    Insert(k+k,l,m,x,y,z);else if(x>=m+1)     Insert(k+k+1,m+1,r,x,y,z);else    Insert(k+k,l,m,x,m,z),Insert(k+k+1,m+1,r,m+1,y,z);//根据f数组的定义修复f数组f[k] = f[k+k]+v[k+k]*(m-l+1)+f[k+k+1]+v[k+k+1]*(r-m);
}
long long calculate(int k,int l,int r,int x,int y)
{
//如果此条件满足，说明要查询的区间与编号k对应的区间相同，我们直接返回编号k对应区间的元素和的表达式即可if(l==x&&r==y)  return v[k]*(r-l+1)+f[k];//由于f数组还未修复，我们不能直接返回递归函数的值，而应该先将它用临时变量存储起来long long res = 0;//标记下放if(v[k]){v[k+k]+=v[k];v[k+k+1]+=v[k];v[k] = 0;}int m = (l+r)/2;if(y<=m)    res = calculate(k+k,l,m,x,y);else if(x>=m+1)     res = calculate(k+k+1,m+1,r,x,y);else    res = calculate(k+k,l,m,x,m)+calculate(k+k+1,m+1,r,m+1,y);f[k] = f[k+k]+v[k+k]*(m-l+1)+f[k+k+1]+v[k+k+1]*(r-m);return res;
}
int main()
{scanf("%d%d",&n,&m);for(int i = 1;i<=n;i++) scanf("%d",&root[i]);buildtree(1,1,n);while(m--){int t;scanf("%d",&t);if(t==1){int x,y;//别忘了k要以long long形式读入！long long k;scanf("%d%d%lld",&x,&y,&k);Insert(1,1,n,x,y,k);}else{int x,y;scanf("%d%d",&x,&y);//注意输出格式！别忘了换行！printf("%lld\n",calculate(1,1,n,x,y));}}return 0;
}

好啦，以上就是本讲的全部内容。若有任何关于文章的问题或批评，都欢迎在评论区指出，博主会进行回复！