洛谷P3372 【模板】线段树 1

题目大意

给出一个数列，有两种操作：

1. 将某区间每一个数加上 k k k
2. 求出某区间每一个数的和

题目分析

假如暴力模拟，时间复杂度 O ( m n ) O(mn) O(mn)，最多只能拿七十分。

既然已经是线段树的模板题了，那么正解一定是线段树，直接写线段树就好了。

不会线段树的请看我的另一篇博客数据结构：线段树

时间复杂度 O ( m l o g n ) O(mlogn) O(mlogn)

C o d e Code Code

#include<iostream>
#include<cstdio>
#define sco 100010
#define ll long long
using namespace std;
ll n,m,f,x,y,z,ans,a[sco];
struct tree{
	ll l,r,data,lz;
}tr[sco*4];
void updata(ll i){tr[i].data=tr[i*2].data+tr[i*2+1].data;}
void down(ll i){
	if(tr[i].l!=0){
		tr[i*2].lz+=tr[i].lz;
		tr[i*2+1].lz+=tr[i].lz;
		tr[i*2].data+=tr[i].lz*(tr[i*2].r-tr[i*2].l+1);
		tr[i*2+1].data+=tr[i].lz*(tr[i*2+1].r-tr[i*2+1].l+1);
		tr[i].lz=0;
	}
	updata(i);
}
void build(ll i,ll l,ll r){
	tr[i].l=l,tr[i].r=r;
	if(l==r){
		tr[i].data=a[l];return;
	}
	ll mid((l+r)>>1);
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	updata(i);
}
void modi(ll i,ll l,ll r,ll k){
	if(l<=tr[i].l && tr[i].r<=r){
		tr[i].data+=(tr[i].r-tr[i].l+1)*k;tr[i].lz+=k;return;
	}
	down(i);
	if(tr[i*2].r>=l)modi(i*2,l,r,k);
	if(tr[i*2+1].l<=r)modi(i*2+1,l,r,k);
	updata(i);
}
ll search(ll i,ll l,ll r){
	if(l<=tr[i].l && tr[i].r<=r){
		return tr[i].data;
	}
	if(tr[i].l>r || tr[i].r<l)return 0;
	down(i);
	ll s(0);
	if(tr[i*2].r>=l)s+=search(i*2,l,r);
	if(tr[i*2+1].l<=r)s+=search(i*2+1,l,r);
	return s;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	for(ll i=1;i<=m;++i){
		scanf("%lld",&f);
		if(f==1){
			scanf("%lld%lld%lld",&x,&y,&z);
			modi(1,x,y,z);continue;
		}
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",search(1,x,y));
	}
	return 0;
}