精华版线段树模板

哈哈哈，打了一上午。。。 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll a[100000+10]; ll lazy[1000000]; struct T{ ll lt,rt; ll sum,mx,mn; }tr[400000+10]; inline void pushup(ll root){ ll son1=root<<1,son2=root<<1|1; tr[root].sum=tr[son1].sum+tr[son2].sum; tr[root].mx=max(tr[son1].mx,tr[son2].mx); tr[root].mn=min(tr[son1].mn,tr[son2].mn); } inline void ct(ll g,ll l,ll r){ tr[g].lt=l,tr[g].rt=r; if(l==r){ tr[g].sum=a[l]; tr[g].mx=tr[g].mn=a[l]; return ; } ll mid=(l+r)>>1; ct(g<<1,l,mid); ct(g<<1|1,mid+1,r); pushup(g); } inline void updata(ll g,ll pos,ll val){ if(tr[g].lt==tr[g].rt&&tr[g].lt==pos){ tr[g].sum+=val; tr[g].mx+=val; tr[g].mn+=val; return ; } ll mid=(tr[g].lt+tr[g].rt)>>1; if(pos<=mid)updata(g<<1,pos,val); else updata(g<<1|1,pos,val); pushup(g); } inline ll qmx(ll g,ll x,ll y){ if(tr[g].lt==x&&tr[g].rt==y){ return tr[g].mx; } ll mid=(tr[g].lt+tr[g].rt)>>1; if(y<=mid)return qmx(g<<1,x,y); else if(x>mid)return qmx(g<<1|1,x,y); else{ ll a=qmx(g<<1,x,mid); ll b=qmx(g<<1|1,mid+1,y); return max(a,b); } } inline ll qmn(ll g,ll x,ll y){ if(tr[g].lt==x&&tr[g].rt==y){ return tr[g].mn; } ll mid=(tr[g].lt+tr[g].rt)>>1; if(y<=mid)return qmn(g<<1,x,y); else if(x>mid)return qmn(g<<1|1,x,y); else{ ll a=qmn(g<<1,x,mid); ll b=qmn(g<<1|1,mid+1,y); return min(a,b); } } void change(ll h,ll l,ll r,ll s,ll e,ll k){ if(l==s&&r==e){ lazy[h]+=k; return; } tr[h].sum+=(e-s+1)*k; ll mid=(l+r)/2; if(s>=mid+1){ change(h*2+1,mid+1,r,s,e,k); } else if(e<=mid){ change(h*2,l,mid,s,e,k); } else { change(h*2,l,mid,s,mid,k); change(h*2+1,mid+1,r,mid+1,e,k); } } inline ll qsum(ll g,ll x,ll y){ if(tr[g].lt==x&&tr[g].rt==y){ return tr[g].sum+lazy[g]*(tr[g].rt-tr[g].lt+1); } ll mid=(tr[g].lt+tr[g].rt)>>1; ll ret=0; if(lazy[g]){ tr[g].sum+=lazy[g]*(tr[g].rt-tr[g].lt+1); change(g*2,tr[g].lt,mid,tr[g].lt,mid,lazy[g]); change(g*2+1,mid+1,tr[g].rt,mid+1,tr[g].rt,lazy[g]); lazy[g]=0; } if(y<=mid)return qsum(g<<1,x,y); else if(x>mid)return qsum(g<<1|1,x,y); else{ ret+=qsum(g<<1,x,mid); ret+=qsum(g<<1|1,mid+1,y); return ret; } } int main(){ ll i,j,k,m,n; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++)scanf("%lld",&a[i]); ct(1,1,n); for(i=1;i<=m;i++){ ll x,y,z; scanf("%lld",&x); if(x==1){ ll u,v,k; scanf("%lld%lld%lld",&u,&v,&k); change(1,1,n,u,v,k); } if(x==2){ ll u,v; scanf("%lld%lld",&u,&v); printf("%lld\n",qsum(1,u,v)); } } return 0; }