区间加线段树
wenge
2020-08-04 05:46:29
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
ll n,ans,q;
ll a[1000005];
struct node{
ll x,add;
}sgt[4*1000005];
void build(ll l,ll r,ll p){
if(l==r){
sgt[p].x=a[l];
return;
}
ll mid=(l+r)>>1;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
sgt[p].x=sgt[p*2].x+sgt[p*2+1].x;
}
ll getsum(ll s,ll t,ll l,ll r,ll p){
if(s<=l&&r<=t){
return sgt[p].x;
}
ll mid=(l+r)>>1;
if(sgt[p].add){
sgt[p*2].x +=sgt[p].add*(mid-l+1);
sgt[p*2+1].x +=sgt[p].add*(r-mid);
sgt[p*2].add +=sgt[p].add;
sgt[p*2+1].add +=sgt[p].add;
sgt[p].add=0;
}
ll sum=0;
if(s<=mid)sum+=getsum(s,t,l,mid,2*p);
if(t>mid)sum+=getsum(s,t,mid+1,r,2*p+1);
return sum;
}
void modify_add(ll s,ll t,ll l,ll r,ll p,ll k){
if(s<=l&&r<=t){
sgt[p].x+=k*(r-l+1);
sgt[p].add+=k;
return;
}
ll mid=(l+r)>>1;
if(sgt[p].add){
sgt[p*2].x +=sgt[p].add*(mid-l+1);
sgt[p*2+1].x +=sgt[p].add*(r-mid);
sgt[p*2].add +=sgt[p].add;
sgt[p*2+1].add +=sgt[p].add;
sgt[p].add=0;
}
if(s<=mid)modify_add(s,t,l,mid,2*p,k);
if(t>mid)modify_add(s,t,mid+1,r,2*p+1,k);
sgt[p].x=sgt[p*2].x+sgt[p*2+1].x;
}
int main(){
//freopen("P1429_6.in","r",stdin);
//freopen("match.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
while(q--){
ll o,s,t,k;
cin>>o>>s>>t;
if(o==1){
cin>>k;
modify_add(s,t,1,n,1,k);
}
else{
cout<<getsum(s,t,1,n,1)<<"\n";
}
}
return 0;
}
```