[模板]正常线段树

　　RT

　　

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 #define int long long
 6 #define maxn 400050
 7 int n,m,ans=0;
 8 int a[100050];
 9 struct node
10 {
11     int l;
12     int r;
13     int w;
14     int f;
15 }tree[maxn];
16
17 void build(int k,int l,int r)
18 {
19     tree[k].l=l;
20     tree[k].r=r;
21     if(l==r)
22     {
23         tree[k].w=a[l];
24         return ;
25     }
26     int mid=(l+r)>>1;
27     build(k<<1,l,mid);
28     build(k<<1|1,mid+1,r);
29     tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
30 }
31 void down(int k)
32 {
33     if(tree[k].w)
34     {
35         tree[k<<1].w+=tree[k].f*(tree[k<<1].r-tree[k<<1].l+1);
36         tree[k<<1|1].w+=tree[k].f*(tree[k<<1|1].r-tree[k<<1|1].l+1);
37         tree[k<<1].f+=tree[k].f;
38         tree[k<<1|1].f+=tree[k].f;
39         tree[k].f=0;
40     }
41 }
42 void area_change(int l,int r,int w,int k)
43 {
44     if(tree[k].l>=l&&r>=tree[k].r)
45     {
46         tree[k].w+=w*(tree[k].r-tree[k].l+1);
47         tree[k].f+=w;
48         return;
49     }
50     down(k);
51     int mid=(tree[k].r+tree[k].l)>>1;
52     if(l<=mid)
53     area_change(l,r,w,k<<1);
54     if(r>mid)
55     area_change(l,r,w,k<<1|1);
56     tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
57 }
58 int area_ask(int k,int l,int r)
59 {
60     if(l<=tree[k].l&&r>=tree[k].r) return tree[k].w;
61     down(k);
62     int mid=(tree[k].l+tree[k].r)>>1;
63     int ans=0;
64     if(l<=mid)ans+=area_ask(k<<1,l,r);
65     if(r>mid)ans+=area_ask(k<<1|1,l,r);
66     return ans;
67 }
68 signed main()
69 {
70     scanf("%lld %lld",&n,&m);
71     for(int i=1;i<=n;i++)
72     {
73         scanf("%lld",&a[i]);
74     }
75
76     build(1,1,n);
77     for(int i=1;i<=m;i++)
78     {
79         int cz;
80         scanf("%lld",&cz);
81         if(cz==1)
82         {
83             int x,y,z;
84             scanf("%lld%lld%lld",&x,&y,&z);
85             area_change(x,y,z,1);
86         }
87         else
88         {
89             int x,y;
90             scanf("%lld%lld",&x,&y);
91             cout<<area_ask(1,x,y)<<endl;;
92         }
93     }
94     return 0;
95 }

-----2021届张若琛