T - A Simple Problem with Integers （线段树&区间修改）

思路：线段树&lazy_tag板子题。

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll tr[N*10];
ll lz[N*10];
void re(int x){
	tr[x]=tr[x<<1]+tr[x<<1|1];
}
void push_down(int x,int len){
	if(lz[x]){
		lz[x<<1]+=lz[x],lz[x<<1|1]+=lz[x];
		tr[x<<1]+=(len-(len>>1))*lz[x];
		tr[x<<1|1]+=(len>>1)*lz[x];
		lz[x]=0;
	}
}
void build(int st,int ed,int x){
	if(st==ed){
		scanf("%lld",&tr[x]);
		return;
	}
	int mid=(st+ed)>>1;
	build(st,mid,x<<1);
	build(mid+1,ed,x<<1|1);
	re(x);
}
void update(int st,int ed,int x,int l,int r,int val){
	if(st>=l&&ed<=r){
		tr[x]+=(ll)(ed-st+1)*val; //更新区间和,并标记lazy_tag 
		lz[x]+=val;
		return;
	}
	push_down(x,ed-st+1);//如果原来有lazy_tag则下放lazy_tag 
	int mid=(st+ed)>>1;
	if(l<=mid) update(st,mid,x<<1,l,r,val);
	if(r>mid)  update(mid+1,ed,x<<1|1,l,r,val);
	re(x);
} 
ll query(int st,int ed,int x,int l,int r){
	if(r<st||l>ed) return 0;
	else if(st>=l&&ed<=r) return tr[x];
	push_down(x,ed-st+1);//当查询到该区间时如果原来有lazy_tag则下放lazy_tag 
	int mid=(st+ed)>>1;
	return query(st,mid,x<<1,l,r)+query(mid+1,ed,x<<1|1,l,r);
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	build(1,n,1);
	/*for(int i=1;i<=20;i++) printf("tr[%d]=%d\n",i,tr[i]); puts(""); */
	while(q--){
		char op;
		int a,b,c;
		scanf("\n%c",&op);
		if(op=='Q'){
		 scanf("%d%d",&a,&b);
		 printf("%lld\n",query(1,n,1,a,b));
		}
		else scanf("%d%d%d",&a,&b,&c),update(1,n,1,a,b,c);
	}
	return 0;
}