阅读量:0
1.运用结构体
// 结构体版 #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define N 100005 #define LL long long #define lc u<<1 #define rc u<<1|1 LL w[N]; struct Tree{ //线段树 LL l,r,sum,add; }tr[N*4]; void pushup(LL u){ //上传 tr[u].sum=tr[lc].sum+tr[rc].sum; } void pushdown(LL u){ //下传 if(tr[u].add){ tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l+1), tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l+1), tr[lc].add+=tr[u].add, tr[rc].add+=tr[u].add, tr[u].add=0; } } void build(LL u,LL l,LL r){ //建树 tr[u]={l,r,w[l],0}; if(l==r) return; LL m=l+r>>1; build(lc,l,m); build(rc,m+1,r); pushup(u); } void change(LL u,LL l,LL r,LL k){ //区修 if(l<=tr[u].l&&tr[u].r<=r){ tr[u].sum+=(tr[u].r-tr[u].l+1)*k; tr[u].add+=k; return; } LL m=tr[u].l+tr[u].r>>1; pushdown(u); if(l<=m) change(lc,l,r,k); if(r>m) change(rc,l,r,k); pushup(u); } LL query(LL u,LL l,LL r){ //区查 if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum; LL m=tr[u].l+tr[u].r>>1; pushdown(u); LL sum=0; if(l<=m) sum+=query(lc,l,r); if(r>m) sum+=query(rc,l,r); return sum; } int main(){ int n,m,op,x,y,k; cin>>n>>m; for(int i=1; i<=n; i ++) cin>>w[i]; build(1,1,n); while(m--){ cin>>op>>x>>y; if(op==2)cout<<query(1,x,y)<<endl; else cin>>k,change(1,x,y,k); } return 0; }2.数组版
// 数组版 #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define N 100005 #define LL long long #define lc u<<1 #define rc u<<1|1 LL w[N]; LL sum[N*4],add[N*4]; //区间和,懒标记 void pushup(LL u){ sum[u]=sum[lc]+sum[rc]; } void pushdown(LL u,LL l,LL r,LL mid){ if(add[u]){ sum[lc]+=add[u]*(mid-l+1); sum[rc]+=add[u]*(r-mid); add[lc]+=add[u]; add[rc]+=add[u]; add[u]=0; } } void build(LL u,LL l,LL r){ sum[u]=w[l]; if(l==r) return; LL mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); pushup(u); } void change(LL u,LL l,LL r,LL x,LL y,LL k){ //区修 if(x>r || y<l) return; //越界 if(x<=l && r<=y){ //覆盖 sum[u]+=(r-l+1)*k; add[u]+=k; return; } LL mid=l+r>>1; pushdown(u,l,r,mid); change(lc,l,mid,x,y,k); //裂开 change(rc,mid+1,r,x,y,k); pushup(u); } LL query(LL u,LL l,LL r,LL x,LL y){ //区查 if(x>r || y<l) return 0; if(x<=l && r<=y) return sum[u]; LL mid=l+r>>1; pushdown(u,l,r,mid); return query(lc,l,mid,x,y)+query(rc,mid+1,r,x,y); } int main(){ int n,m,op,x,y,k; cin>>n>>m; for(int i=1; i<=n; i ++) cin>>w[i]; build(1,1,n); while(m--){ cin>>op>>x>>y; if(op==1) cin>>k,change(1,1,n,x,y,k); else cout<<query(1,1,n,x,y)<<endl; } return 0; }
