P3372 【模板】线段树 1

画图灵感来源线段树3那道题，为了弄懂线段树3，所以从线段树1开始画图模拟一遍，进行深刻的算法流程理解

》

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N];struct Node
{int l,r;ll sum;ll add;
}tr[N*4];void pushup(int u)
{tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum);
}void pushdown(int u)
{auto &root=tr[u], &left=tr[u<<1], &right=tr[u<<1|1];if(tr[u].add){left.add+=root.add,left.sum+=(ll)(left.r-left.l+1)*root.add;right.add+=root.add,right.sum+=(ll)(right.r-right.l+1)*root.add;root.add=0;}
}void build(int u, int l, int r)
{if(l==r) tr[u]={l,r,a[r],0};else{tr[u].l=l,tr[u].r=r;int mid=tr[u].l+tr[u].r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u, int l,int r, ll v)
{if(tr[u].l>=l&&tr[u].r<=r){tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*v;tr[u].add+=v;//pushup(u);}else{pushdown(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid) modify(u<<1,l,r,v);if(r>mid) modify(u<<1|1,l,r,v);pushup(u);}
}ll query(int u, int l, int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;else{pushdown(u);int mid=tr[u].l+tr[u].r>>1;ll res=0;if(l<=mid) res+=query(u<<1,l,r);if(r>mid) res+=query(u<<1|1,l,r);return res;}
}signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(m--){int op,x,y;ll k;cin>>op>>x>>y;if(op==1){cin>>k;modify(1,x,y,k);}else{cout<<query(1,x,y)<<endl;}}return 0;
}