洛谷P3372 线段树
板子题,但也是我写的(抄的)第一道线段树的题。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int a[N];
ll d[N<<2],lazy[N<<2];void build(int l,int r,int p)//build tree
{if(l==r){d[p]=a[l];return;}int m=l+((r-l)>>1);build(l,m,p<<1),build(m+1,r,(p<<1)|1);d[p]=d[p<<1]+d[(p<<1)|1];
}void update(int l,int r,int s,int e,int x,int p)
{if(l<=s&&r>=e){d[p]+=(e-s+1)*x,lazy[p]+=x;return;}int m=s+((e-s)>>1);if(lazy[p]){d[p<<1]+=(m-s+1)*lazy[p];d[(p<<1)|1]+=(e-m)*lazy[p];lazy[p<<1]+=lazy[p];lazy[(p<<1)|1]+=lazy[p];lazy[p]=0;}if(l<=m) update(l,r,s,m,x,p<<1);if(r>m) update(l,r,m+1,e,x,(p<<1)|1);d[p]=d[p<<1]+d[(p<<1)|1];
}ll getsum(int l,int r,int s,int e,int p)
{if(l<=s&&r>=e)return d[p];int m=s+((e-s)>>1);ll res=0;if(lazy[p]){d[p<<1]+=(m-s+1)*lazy[p];d[(p<<1)|1]+=(e-m)*lazy[p];lazy[p<<1]+=lazy[p];lazy[(p<<1)|1]+=lazy[p];lazy[p]=0;}if(l<=m) res+=getsum(l,r,s,m,p<<1);if(r>m) res+=getsum(l,r,m+1,e,(p<<1)|1);return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1);while(m--){int op;cin>>op;if(op==1){int l,r,x;cin>>l>>r>>x;update(l,r,1,n,x,1);}else{int l,r;cin>>l>>r;cout<<getsum(l,r,1,n,1)<<'\n';}}return 0;
}
几乎是照着别人的敲的,但是也没事,懂了就行。