P3372 【模板】线段树 1

题目的神奇传送门

模板题呦，听老师说第一遍打板子很难？？可是我第一遍打完之后就改了一个小地方就过了？？emmmm可能是我太聪明了吧~~~

那不多bb，具体一点的解释在代码里

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
#define ll long long

int n,m;
ll a[N],p[N];

void build(int k,int l,int r){//建树
	if(l==r){//当到达根节点的时候再读入，不用保存原数组
		int u;
		scanf("%d",&u);
		a[k]=u;
		return;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	a[k]=a[k*2]+a[k*2+1];//从下往上处理
}

void add(int k,int l,int r,int lo,int ro,int q){
	if(l>ro||r<lo){//无交集的情况
		return;
	}
	if(l==r){//到达根节点
		a[k]+=q;
		return;
	}
	if(l>=lo&&r<=ro){//覆盖的情况直接返回值，并用懒惰标记
		p[k]+=q;
		a[k]+=q*(r-l+1);
		return;
	}//下面为有交集但无覆盖
	int mid=(l+r)/2;
	if(p[k]){//若有懒惰标记，则进行push_down操作
		p[k*2]+=p[k];
		p[k*2+1]+=p[k];
		a[k*2]+=(mid-l+1)*p[k];
		a[k*2+1]+=(r-mid)*p[k];
		p[k]=0;
	}
	add(k*2,l,mid,lo,ro,q);//左右子树
	add(k*2+1,mid+1,r,lo,ro,q);
	a[k]=a[k*2]+a[k*2+1];//从下到上处理
}

ll getsum(int k,int l,int r,int lo,int ro){//求和
	if(l>ro||r<lo){//无交集
		return 0;
	}
	if(l>=lo&&r<=ro){//覆盖
		return a[k];
	}
	int mid=(l+r)/2;
	if(p[k]){//push_down
		p[k*2]+=p[k];
		p[k*2+1]+=p[k];
		a[k*2]+=(mid-l+1)*p[k];
		a[k*2+1]+=(r-mid)*p[k];
		p[k]=0;
	}
	return getsum(k*2,l,mid,lo,ro)+getsum(k*2+1,mid+1,r,lo,ro);//返回和值
}

int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);//建树
	while(m--){
		int l,r,t;
		scanf("%d%d%d",&t,&l,&r);
		if(t==1){
			int k;
			scanf("%d",&k);
			add(1,1,n,l,r,k);//l-r增加k
		}
		else{
			printf("%lld
",getsum(1,1,n,l,r));//求和
		}
		//for(int i=1;i<=2*n;i++){//调试用
		//	printf("%d(%d) ",a[i],p[i]);
		//}
		//printf("
");
	}
	return 0;
}

　　白白