本文共 1847 字，大约阅读时间需要 6 分钟。
线段树的裸题。
给定N个数，有两种操作，一种使[a,b]区间内所有数加上c，另一种询问[a,b]区间内所有数的和。
代码如下：
#include #include #include #include using namespace std;typedef long long ll;const int maxn=1e5+6;const int inf=0x3f3f3f3f;ll a[maxn];struct Node{ int l,r; ll lazy,sum; //lazy为更新延迟标记，sum记录当前区间的数的总和}tr[maxn<<2];void push_up(int rt) { tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;}void push_down(int rt){ tr[rt<<1].lazy+=tr[rt].lazy; //注意这里是+=，不是= tr[rt<<1|1].lazy+=tr[rt].lazy; tr[rt<<1].sum+=(tr[rt<<1].r-tr[rt<<1].l+1)*tr[rt].lazy; tr[rt<<1|1].sum+=(tr[rt<<1|1].r-tr[rt<<1|1].l+1)*tr[rt].lazy; tr[rt].lazy=0; //最后记得记得要赋值为0}void build(int rt,int l,int r){ tr[rt].l=l; tr[rt].r=r; tr[rt].lazy=0; if(tr[rt].l==tr[rt].r) { tr[rt].sum=a[l]; return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); push_up(rt);}void update(int rt,int l,int r,ll val){ if(l<=tr[rt].l&&tr[rt].r<=r) { tr[rt].lazy+=val; //这里也是要+=，不是= tr[rt].sum+=(tr[rt].r-tr[rt].l+1)*val; return; } if(tr[rt].l==tr[rt].r) return; if(tr[rt].lazy) push_down(rt); int mid=(tr[rt].r+tr[rt].l)>>1; if(mid =r) update(rt<<1,l,r,val); else { update(rt<<1,l,mid,val); update(rt<<1|1,mid+1,r,val); } push_up(rt); //最后面这个push_up别忘了}void query(int rt,int l,int r,ll &sum){ if(l<=tr[rt].l&&tr[rt].r<=r) { sum+=tr[rt].sum; return; } if(tr[rt].l==tr[rt].r) return; if(tr[rt].lazy) push_down(rt); //query函数内也要记得用push_down函数 int mid=(tr[rt].l+tr[rt].r)>>1; if(mid =r) query(rt<<1,l,r,sum); else { query(rt<<1,l,mid,sum); query(rt<<1|1,mid+1,r,sum); }}int main(){ int n,q; while(~scanf("%d%d",&n,&q)) { for(int i=1;i<=n;++i) scanf("%lld",&a[i]); build(1,1,n); while(q--) { char s[2]; int l,r; scanf("%s%d%d",s,&l,&r); if(s[0]=='Q') { ll sum=0; query(1,l,r,sum); printf("%lld\n",sum); } else { ll val; scanf("%lld",&val); update(1,l,r,val); } } } return 0;}
转载地址：http://zzdci.baihongyu.com/