区间线段树：
const int MAXM=100000; int a[MAXM+5]; ll st[(MAXM<<2)+5],lazy[(MAXM<<2)+5]; inline void push_up(int o) { st[o]=st[o<<1]+st[o<<1|1]; } inline void push_down(int o,int l,int r) { if(lazy[o]) { lazy[o<<1]+=lazy[o]; lazy[o<<1|1]+=lazy[o]; int m=(l+r)>>1; st[o<<1]+=lazy[o]*(m-l+1); st[o<<1|1]+=lazy[o]*(r-m); lazy[o]=0; } } void build(int o,int l,int r) { if(l==r) st[o]=a[l]; else { int m=(l+r)>>1; build(o<<1,l,m); build(o<<1|1,m+1,r); push_up(o); } lazy[o]=0; } void update(int o,int l,int r,int a,int b,ll v) { if(a<=l&&r<=b) { lazy[o]+=v; st[o]+=v*(r-l+1); return; } else { push_down(o,l,r); int m=(l+r)>>1; if(a<=m) update(o<<1,l,m,a,b,v); if(b>=m+1) update(o<<1|1,m+1,r,a,b,v); push_up(o); } } ll query(int o,int l,int r,int a,int b) { if(a<=l&&r<=b) { return st[o]; } else { push_down(o,l,r); int m=(l+r)>>1; ll ans=0; if(a<=m) ans=ans+query(o<<1,l,m,a,b); if(b>=m+1) ans=ans+query(o<<1|1,m+1,r,a,b); return ans; } }单点线段树就把lazy相关的直接给去掉就行了。
单点线段树：
const int MAXM=100000; int a[MAXM+5]; int st[(MAXM<<2)+5]; inline void push_up(int o) { st[o]=st[o<<1]+st[o<<1|1]; } void build(int o,int l,int r) { if(l==r){ st[o]=a[l]; } else { int m=(l+r)>>1; build(o<<1,l,m); build(o<<1|1,m+1,r); push_up(o); } } void update(int o,int l,int r,int x,int v) { if(l==r) { st[o]=v; return; } else { int m=(l+r)>>1; if(x<=m) update(o<<1,l,m,x,v); else if(x>=m+1) update(o<<1|1,m+1,r,x,v); push_up(o); } } int query(int o,int l,int r,int a,int b) { if(a<=l&&r<=b) { return st[o]; } else { int m=(l+r)>>1; int ans=0; if(a<=m) ans=query(o<<1,l,m,a,b); if(b>=m+1) ans+=query(o<<1|1,m+1,r,a,b); return ans; } }转载于:https://www.cnblogs.com/Yinku/p/11039664.html
