P3372 【模板】线段树 1

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll N=1000010;
 5 ll n,m;
 6 ll a[N];
 7 
 8 struct Node{
 9     ll it;
10     ll l;
11     ll r;
12     ll data;
13 }tree[N];
14 
15 void build(ll rt,ll l,ll r){
16     tree[rt].l=l;
17     tree[rt].r=r;
18     tree[rt].it=0;
19     if(l==r){
20         tree[rt].data=a[l];
21         return ;
22     }
23     ll mid = (l+r)>>1;
24     build(rt*2,l,mid);
25     build(rt*2+1,mid+1,r);
26     tree[rt].data=tree[rt*2].data+tree[rt*2+1].data;
27     return ;
28 }
29 
30 void push_down(ll rt){
31     if(tree[rt].it!=0){
32         tree[rt*2].it+=tree[rt].it;
33         tree[rt*2+1].it+=tree[rt].it;
34         ll mid = (tree[rt].l+tree[rt].r)>>1;
35         tree[rt*2].data+=tree[rt].it*(mid-tree[rt*2].l+1);
36         tree[rt*2+1].data+=tree[rt].it*(tree[rt*2+1].r-mid);
37         tree[rt].it=0;
38     }
39     return ;
40 }
41 
42 void up_data(ll rt,ll l,ll r,ll k){
43     if(tree[rt].l>=l&&tree[rt].r<=r){
44         tree[rt].data+=k*(tree[rt].r-tree[rt].l+1);
45         tree[rt].it+=k;
46         return ;
47     }
48     push_down(rt);
49     if(tree[rt*2].r>=l){
50         up_data(rt*2,l,r,k);
51     }
52     if(tree[rt*2+1].l<=r){
53         up_data(rt*2+1,l,r,k);
54     }
55     tree[rt].data=tree[rt*2].data+tree[rt*2+1].data;
56     return ;
57 }
58 
59 ll search(ll rt,ll l,ll r){
60     if(tree[rt].l>=l&&tree[rt].r<=r){
61         return tree[rt].data;
62     }
63     push_down(rt);
64     ll num=0;
65     if(tree[rt*2].r>=l){
66         num+=search(rt*2,l,r);
67     }
68     if(tree[rt*2+1].l<=r){
69         num+=search(rt*2+1,l,r);
70     }
71     return num;
72 }
73 
74 int main(){
75     scanf("%lld%lld",&n,&m);
76     for(ll i=1;i<=n;i++){
77         scanf("%lld",&a[i]);
78     }
79     build(1,1,n);
80     for(ll i=1;i<=m;i++){
81         ll go;
82         scanf("%lld",&go);
83         if(go==1){
84             ll a,b,c;
85             scanf("%lld%lld%lld",&a,&b,&c);
86             up_data(1,a,b,c);
87         }
88         if(go==2){
89             ll a,b;
90             scanf("%lld%lld",&a,&b);
91             printf("%lld
",search(1,a,b));
92         }
93     }
94     return 0;
95 }