线段树

https://www.luogu.com.cn/problem/P3372

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define lson l,mid,rt<<1
 5 #define rson mid+1,r,rt<<1|1 
 6 #define ll long long
 7 const int mac=1e5+50;
 8 ll tree[mac<<2],a[mac];
 9 ll lazy[mac<<2];
10 void push_up(int rt){
11     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
12 }
13 void push_down(int l,int r,int rt){
14     if(lazy[rt]!=0){
15         int mid=(l+r)>>1;
16         tree[rt<<1]+=lazy[rt]*(mid-l+1);
17         tree[rt<<1|1]+=lazy[rt]*(r-mid);
18         lazy[rt<<1]+=lazy[rt];
19         lazy[rt<<1|1]+=lazy[rt];
20         lazy[rt]=0;
21     }
22 }
23 void build(int l,int r,int rt){
24     if(l==r){
25         scanf("%lld",&tree[rt]);
26         return ;
27     }
28     int mid=(l+r)>>1;
29     build(lson);
30     build(rson);
31     push_up(rt);
32 }
33 ll query(int l,int r,int rt,int L,int R,ll ans){
34     if(r<L||l>R)
35         return ans;
36     if(l>=L&&r<=R){
37         return ans+tree[rt];
38     }
39     push_down(l,r,rt);
40     int mid=(l+r)>>1;
41     if(L<=mid){
42         ans=query(lson,L,R,ans);
43     }
44     if(R>mid){
45         ans=query(rson,L,R,ans);
46     }
47     return ans;
48 }
49 void update(int l,int r,int rt,int L,int R,ll z){
50     if(l>R||r<L)
51         return;
52     if(l>=L&&r<=R){
53         tree[rt]+=(r-l+1)*z;
54         lazy[rt]+=z;
55         return ;
56     }
57     push_down(l,r,rt);
58     int mid=(l+r)>>1;
59     if(L<=mid){
60         update(lson,L,R,z);
61     }
62     if(R>mid){
63         update(rson,L,R,z);
64     }
65     push_up(rt);
66 }
67 int main(){
68     int i,n,m,k,x,y;
69     ll ans=0,z;
70     scanf("%d %d",&n,&m);
71     build(1,n,1);
72     while(m--){
73         scanf("%d",&k);
74         switch(k){
75             case 1:{
76                 scanf("%d %d %lld",&x,&y,&z);
77                 update(1,n,1,x,y,z);
78                 break;
79             }
80             case 2:{
81                 scanf("%d %d",&x,&y);
82                 ans=query(1,n,1,x,y,ans);
83                 printf("%lld\n",ans);
84                 ans=0;
85                 break;
86             }
87         }
88     }
89 }