信息学奥赛各大算法模板

#include<bits/stdc++.h> using namespace std; #define N 100005 typedef long long ll; //区间修改，求区间和 ll tree[N*4],a[N],tag[N*4],n,m; void pushup(ll cur){ tree[cur]=tree[cur<<1]+tree[cur<<1|1];//维护区间和 // tree[cur]=min(tree[cur<<1],tree[cur<<1|1]);//维护最小值 } void pushdown(ll cur,ll l, ll r){ //标记下移 if(tag[cur]>0){ tag[cur<<1]+=tag[cur]; tag[cur<<1|1]+=tag[cur]; //节点更新 int mid=(l+r)>>1; tree[cur<<1]+=(mid-l+1)*tag[cur]; tree[cur<<1|1]+=(r-mid)*tag[cur]; tag[cur]=0; } } void update(ll cur,ll l,ll r,ll L,ll R,ll k){//将区间[L,R]内的数据增加k if(L<=l && r<=R){//在目标区间内 tag[cur]+=k; tree[cur]+=(r-l+1)*k; return; } pushdown(cur,l,r) ;//否则标记下移 ll mid=(l+r)>>1; if(L<=mid)update(cur<<1,l,mid,L,R,k); if(R>mid) update(cur<<1|1,mid+1,r,L,R,k); pushup(cur); } ll query(ll cur,ll l,ll r,ll L,ll R){//查询区间和 if(L<=l && r<=R){ return tree[cur]; } pushdown(cur,l,r); ll mid=(l+r)>>1; ll ans=0; if(L<=mid)ans+=query(cur<<1,l,mid,L,R); if(R>mid) ans+=query(cur<<1|1,mid+1,r,L,R); return ans; } void build(ll cur,ll l, ll r){//构建线段树 if(l==r){ tree[cur]=a[r]; return; } ll mid=(l+r)>>1; build(cur<<1,l,mid); build(cur<<1|1,mid+1,r); pushup(cur); } int main(){ scanf("%lld %lld",&n,&m); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,1,n); ll t,x,y,k; for(ll i=1;i<=m;i++){ scanf("%lld",&t); if(t==1){ scanf("%lld %lld %lld",&x,&y,&k); update(1,1,n,x,y,k); } if(t==2){ scanf("%lld %lld",&x,&y); printf("%lld\n",query(1,1,n,x,y)); } } return 0; }