codevs 1082 线段树练习3 模板题

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 long long a[2000003],sum[10000003],add[10000003],n;
 6 void pushup(long long rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
 7 void build(long long l,long long r,long long rt)
 8 {
 9     if (l==r){sum[rt]=a[l];return;}
10     long long mid=(l+r)>>1;
11     build(l,mid,rt<<1);
12     build(mid+1,r,rt<<1|1);
13     pushup(rt);
14 }
15 void pushdown(long long rt,long long ln,long long rn)
16 {
17     if (add[rt])
18     {
19         add[rt<<1]+=add[rt];
20         add[rt<<1|1]+=add[rt];
21         sum[rt<<1]+=add[rt]*ln;
22         sum[rt<<1|1]+=add[rt]*rn;
23         add[rt]=0;
24     }
25 }
26 void updata(long long L,long long R,long long C,long long l,long long r,long long rt)
27 {
28     if ((L<=l)&&(r<=R))
29     {
30         sum[rt]+=C*(r-l+1);
31         add[rt]+=C; return;
32     }
33     long long mid=(l+r)>>1;
34     pushdown(rt,mid-l+1,r-mid);
35     if (L<=mid) updata(L,R,C,l,mid,rt<<1);
36     if (R>mid) updata(L,R,C,mid+1,r,rt<<1|1);
37     pushup(rt);
38 }
39 long long query(long long L,long long R,long long l,long long r,long long rt)
40 {
41     if ((L<=l)&&(r<=R)) return sum[rt];
42     long long mid=(l+r)>>1;
43     pushdown(rt,mid-l+1,r-mid);
44     long long ans=0;
45     if (L<=mid) ans+=query(L,R,l,mid,rt<<1);
46     if (R>mid) ans+=query(L,R,mid+1,r,rt<<1|1);
47     return ans;
48 }
49 int main()
50 {
51     scanf("%lld",&n);
52     long long i,j,q,t,l,r,x;
53     for (i=1;i<=n;++i) scanf("%lld",&a[i]);
54     build(1,n,1);
55     scanf("%lld",&q);
56     for (i=1;i<=q;++i)
57     {
58         scanf("%lld",&t);
59         if (t==1)
60         {
61             scanf("%lld%lld%lld",&l,&r,&x);
62             updata(l,r,x,1,n,1);
63         }
64         else
65         {
66             scanf("%lld%lld",&l,&r);
67             printf("%lld
",query(l,r,1,n,1));
68         }
69     }
70     return 0;
71 }
NOI 2017 Bless All