P3372 【模板】线段树 1

#include<bits/stdc++.h>
using namespace std;
int n,m,flag;
long long x,y,k,a[1000010];
struct node{
	int l,r,lazy;
	long long sum;
}tree[4000010];
void build(int rt,int l,int r){
	if(l==r){
		tree[rt].l=l,tree[rt].r=r,tree[rt].lazy=0;
		tree[rt].sum=a[r];
	}int mid=(l+r)/2;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	tree[rt].l=l,tree[rt].r=r,tree[rt].lazy=0;
	tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;	
}void push_down(int rt){
	if(tree[rt].lazy==0){
		return;
	}tree[rt*2].sum=(tree[rt*2].r-tree[rt*2].l+1)*tree[rt*2].lazy;
	tree[rt*2+1].sum=(tree[rt*2+1].r-tree[rt*2+1].l+1)*tree[rt*2+1].lazy;
	tree[rt*2].lazy+=tree[rt].lazy,tree[rt*2+1].lazy+=tree[rt].lazy;
	tree[rt].lazy=0;
}void updata(int rt,int l,int r,long long k){
	if(l==tree[rt].l&&r==tree[rt].r){
		tree[rt].sum+=(l-r+1)*k,tree[rt].lazy+=k;
		return;
	}push_down(rt);
	int mid=(tree[rt].l+tree[rt].r)/2;
	if(r<=mid){
		updata(rt*2,l,r,k);
	}else if(l>mid){
		updata(rt*2+1,l,r,k);
	}else{
		updata(rt*2,l,mid,k);
		updata(rt*2+1,mid+1,r,k);
	}tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
}long long query(int rt,int l,int r){
	if(l==tree[rt].l&&r==tree[rt].r){
		return tree[rt].sum;
	}push_down(rt);
	int mid=(tree[rt].l+tree[rt].r)/2;
	long long sum=0;	
	if(r<=mid){
		sum+=query(rt*2,l,r);
	}else if(l>mid){
		sum+=query(rt*2+1,l,r);
	}else{
		sum+=query(rt*2,l,mid);
		sum+=query(rt*2+1,mid+1,r);
	}	
}int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}build(1,1,n);
	while(m --> 0){
		scanf("%d",&flag);
		if(flag==1){
			scanf("%d%d%lld",&x,&y,&k);
			updata(1,x,y,k);
		}else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(1,x,y));
		}
	}
	return 0;
}