codevs 1082 线段树练习3 模板题

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[],sum[],add[],n;
void pushup(long long rt){sum[rt]=sum[rt<<]+sum[rt<<|];}
void build(long long l,long long r,long long rt)
{
if (l==r){sum[rt]=a[l];return;}
long long mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
pushup(rt);
}
void pushdown(long long rt,long long ln,long long rn)
{
if (add[rt])
{
add[rt<<]+=add[rt];
add[rt<<|]+=add[rt];
sum[rt<<]+=add[rt]*ln;
sum[rt<<|]+=add[rt]*rn;
add[rt]=;
}
}
void updata(long long L,long long R,long long C,long long l,long long r,long long rt)
{
if ((L<=l)&&(r<=R))
{
sum[rt]+=C*(r-l+);
add[rt]+=C; return;
}
long long mid=(l+r)>>;
pushdown(rt,mid-l+,r-mid);
if (L<=mid) updata(L,R,C,l,mid,rt<<);
if (R>mid) updata(L,R,C,mid+,r,rt<<|);
pushup(rt);
}
long long query(long long L,long long R,long long l,long long r,long long rt)
{
if ((L<=l)&&(r<=R)) return sum[rt];
long long mid=(l+r)>>;
pushdown(rt,mid-l+,r-mid);
long long ans=;
if (L<=mid) ans+=query(L,R,l,mid,rt<<);
if (R>mid) ans+=query(L,R,mid+,r,rt<<|);
return ans;
}
int main()
{
scanf("%lld",&n);
long long i,j,q,t,l,r,x;
for (i=;i<=n;++i) scanf("%lld",&a[i]);
build(,n,);
scanf("%lld",&q);
for (i=;i<=q;++i)
{
scanf("%lld",&t);
if (t==)
{
scanf("%lld%lld%lld",&l,&r,&x);
updata(l,r,x,,n,);
}
else
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",query(l,r,,n,));
}
}
return ;
}
上一篇:centos的vi常用用法


下一篇:iOS开发 UIWebView+JavaScript 交互总结