线段树标版

  1 //s d s
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstdlib>
  5 using namespace std;
  6 const int N=5000006;
  7 long long  a[N],sum[N];int miku[N];
  8 long long  b,c,d,e;
  9 
 10 void update(int rt)
 11 {
 12     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 13 }
 14 
 15 void build(int l,int r,int rt)
 16 {
 17     if(l==r)
 18     {
 19         sum[rt]=a[l];
 20         return ;
 21     }
 22     int m=(l+r)>>1;
 23     build(l,m,rt<<1);
 24     build(m+1,r,rt<<1|1);
 25     update(rt);
 26 }
 27 void pushdown(int l,int r,int m,int rt)
 28 {
 29     sum[rt<<1]+=miku[rt]*(m-l+1);
 30     sum[rt<<1|1]+=miku[rt]*(r-m);
 31     miku[rt<<1]+=miku[rt];
 32     miku[rt<<1|1]+=miku[rt];
 33     miku[rt]=0;
 34     
 35  } 
 36 void midify_interval(int l,int r,int rt,int nowl,int nowr,int neww)
 37 {
 38     if(nowl==l&&nowr==r)
 39     {
 40         miku[rt]+=neww;
 41         sum[rt]+=neww*(r-l+1);
 42         return ;
 43     }
 44     int m=(l+r)>>1;
 45     pushdown(l,r,m,rt);
 46     if(nowr<=m) midify_interval(l,m,rt<<1,nowl,nowr,neww);
 47     else if(nowl>m) midify_interval(m+1,r,rt<<1|1,nowl,nowr,neww);
 48     else 
 49     {
 50         midify_interval(l,m,rt<<1,nowl,m,neww);
 51         midify_interval(m+1,r,rt<<1|1,m+1,nowr,neww);
 52     }
 53     update(rt);
 54 }
 55 
 56 long long  query(int l,int r,int rt,int nowl,int nowr)
 57 {
 58     if(nowl<=l&&nowr>=r)
 59     {
 60         return sum[rt];
 61     }
 62     int m=(r+l)>>1;
 63     pushdown(l,r,m,rt);
 64     long long  ans=0;
 65     if(nowl<=m) ans+=query(l,m,rt<<1,nowl,nowr);
 66     if(nowr>m)ans+=query(m+1,r,rt<<1|1,nowl,nowr);
 67     return ans;
 68 }
 69 
 70 int query_node(int l,int r,int rt,int nowrt)
 71 {
 72     if(l==r)
 73     {
 74         return sum[rt];
 75     }
 76     int m=(r+l)/2;
 77     sum[rt+rt]+=miku[rt]*(m-l+1);
 78     sum[rt+rt+1]+=miku[rt]*(r-m);
 79     miku[rt+rt]+=miku[rt];
 80     miku[rt+rt+1]+=miku[rt];
 81     miku[rt]=0;
 82     int ans=0;
 83     if(nowrt<=m) ans=query_node(l,m,rt<<1,nowrt);
 84     else if(nowrt>m)  ans=query_node(m+1,r,rt<<1|1,nowrt);
 85     return ans;
 86 }
 87 
 88 int main()
 89 {
 90     int n;
 91     scanf("%lld",&n);
 92     for(int i=1;i<=n;i++)scanf("%lld",a+i);
 93     build(1,n,1);
 94     int m;
 95     scanf("%lld",&m);
 96     
 97     for(int i=1;i<=m;i++)
 98     {
 99         scanf("%lld",&b);
100         if(b==1)
101         {
102             scanf("%lld%lld%lld",&c,&d,&e);
103             midify_interval(1,n,1,c,d,e);
104         }
105         if(b==2)
106         {
107             scanf("%lld%lld",&c,&d);
108             printf("%lld
",query(1,n,1,c,d));
109         }
110     }
111     return 0;
112 
113 }