帮同学问

题目

#include <bits/stdc++.h>
using namespace std;
long long tree[400005],n,num[100005],lazy[400005],m;
void build(long long root,long long start,long long end) {
	if(start==end) {
		tree[root]=num[start];
		return;
	}
	int mid=(start+end)>>1;
	build(root*2,start,mid);
	build(root*2+1,mid+1,end);
	tree[root]=tree[root*2]+tree[root*2+1];
}
void lazydown(long long root,long long start,long long end) {
	if(!lazy[root] || start==end) {
		return;
	}
	int mid=(start+end)>>1;
	tree[root*2]+=lazy[root]*(mid-start+1);
	tree[root*2+1]+=lazy[root]*(end-mid);
	lazy[root*2]+=lazy[root];
	lazy[root*2+1]+=lazy[root];
	lazy[root]=0;
}
int query(long long root,long long start,long long end,long long l,long long r) {
	if(l<=start && r>=end) {
		return tree[root];
	}
	lazydown(root,start,end);
	int mid=(start+end)>>1;
	if(r<=mid) {
		return query(root*2,start,mid,l,r);
	} else if(l>mid) {
		return query(root*2+1,mid+1,end,l,r);
	} else {
		return query(root*2+1,mid+1,end,l,r)+query(root*2,start,mid,l,r);
	}
}
void update(long long root,long long start,long long end,long long l,long long r,long long k) {
	if(l<=start && r>=end) {
		tree[root]+=k*(start-end+1);
		lazy[root]+=k;
		return;
	}
	lazydown(root,start,end);
	int mid=(start+end)>>1;
	if(r<=mid) {
		update(root*2,start,mid,l,r,k);
	} else if(l>mid) {
		update(root*2+1,mid+1,end,l,r,k);
	} else {
		update(root*2+1,mid+1,end,l,r,k);
		update(root*2,start,mid,l,r,k);
	}
	tree[root]=tree[root*2]+tree[root*2+1];
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++)cin>>num[i];
	build(1,1,n);
	for(int i=1; i<=m; i++) {
		int type,x=0,y=0,k=0;
		cin>>type;
		if(type==1) {
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		} else {
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<endl;
		}
	}
}