P3372 【模板】线段树1

liubo

题目描述如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：
输出包含若干行整数，即为所有操作2的结果。
输入输出样例输入样例#1：[url=]复制[/url]5 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4
输出样例#1：[url=]复制[/url]11820

说明时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：

倚窗倾听风吹雨

1. #include<iostream>
   
2. #define FOR(i,a,b) for(register int i=a;i<=b;i++)
   
3. using namespace std;
   
4. typedef long long int ll;
   
5. const int N=100005;
   
6. int L,R,m,n;
   
7. ll a[N],sum[N<<2],add[N<<2],ans,ad,k;
   
8. inline void PushUp(int l,int r,int p){sum[p]=sum[p<<1]+sum[(p<<1)|1]+add[p]*(r-l+1);}
   
9. void BuildTree(int l,int r,int p)
   
10. {
    
11.     if(l==r){sum[p]=a[l];return;}
    
12.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
13.     BuildTree(l,mid,ls);
    
14.     BuildTree(mid+1,r,rs);
    
15.     PushUp(l,r,p);return;
    
16. }
    
17. void Add(int l,int r,int p)
    
18. {
    
19.     if(L<=l && r<=R){sum[p]+=k*(r-l+1);add[p]+=k;return;}
    
20.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
21.     if(L<=mid) Add(l,mid,ls);
    
22.     if(R>mid) Add(mid+1,r,rs);
    
23.     PushUp(l,r,p);return;
    
24. }
    
25. void query(int l,int r,int p)
    
26. {
    
27.     if(L<=l && r<=R){ans+=sum[p]+ad*(r-l+1);return;}
    
28.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
29.     ad+=add[p];
    
30.     if(L<=mid)query(l,mid,ls);
    
31.     if(R>mid)query(mid+1,r,rs);
    
32.     ad-=add[p];return;
    
33. }
    
34. void print(int l,int r,int p)
    
35. {
    
36.     cout<<l<<" "<<r<<" "<<p<<" "<<sum[p]<<" "<<add[p]<<endl;
    
37.     if(l==r)return;
    
38.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
39.     print(l,mid,ls);
    
40.     print(mid+1,r,rs);
    
41. }
    
42. int main()
    
43. {
    
44.     cin>>n>>m;
    
45.     FOR(i,1,n)cin>>a[i];
    
46.     BuildTree(1,n,1);
    
47.     while(m--)
    
48.     {
    
49.         int x;
    
50.         cin>>x>>L>>R;
    
51.         if(x==1)
    
52.         {
    
53.             cin>>k;
    
54.             Add(1,n,1);
    
55.          ///   print(1,n,1);
    
56.          ///   cout<<"---------------"<<endl;
    
57.         }
    
58.         else
    
59.         {
    
60.             ans=0;ad=0;
    
61.             query(1,n,1);
    
62.             cout<<ans<<endl;
    
63.         }
    
64.     }
    
65.     return 0;
    
66. }
    

复制代码

zhwang

1. #include<cstdio>
   
2. #define int long long
   
3. int a[100001];
   
4. int he;
   
5. int n,m,k,l,r,x;
   
6. struct node
   
7. {
   
8.     int left;
   
9.     int right;
   
10.     int sum;
    
11.     int tag;
    
12. }tree[400001];
    
13. void setup(int root,int start,int end)
    
14. {
    
15.     tree[root].tag=0;
    
16.     tree[root].left=start;
    
17.     tree[root].right=end;
    
18.     if(start==end)
    
19.     {
    
20.         tree[root].sum=a[start];
    
21.     }
    
22.     else
    
23.     {
    
24.         setup(root*2,start,start+(end-start)/2);
    
25.         setup(root*2+1,start+(end-start)/2+1,end);
    
26.         tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
    
27.     }
    
28. }
    
29. void add(int start,int end,int root,int num)
    
30. {
    
31.     if(tree[root].left==start&&tree[root].right==end)
    
32.     {
    
33.         tree[root].tag+=num;
    
34.         return;
    
35.     }
    
36.     else
    
37.     {
    
38.         if(end<=tree[root*2].right)
    
39.         {
    
40.             add(start,end,2*root,num);
    
41.         }
    
42.         else
    
43.         {
    
44.             if(start>=tree[root*2+1].left)
    
45.             {
    
46.                 add(start,end,2*root+1,num);
    
47.             }
    
48.             else
    
49.             {
    
50.                 add(start,tree[2*root].right,2*root,num);
    
51.                 add(tree[2*root+1].left,end,2*root+1,num);
    
52.             }
    
53.         }
    
54.     }
    
55.     tree[2*root].tag+=tree[root].tag;
    
56.     tree[2*root+1].tag+=tree[root].tag;
    
57.     tree[root].tag=0;
    
58.     tree[root].sum=tree[2*root].sum+tree[2*root+1].sum+tree[2*root].tag*(tree[2*root].right-tree[2*root].left+1)+tree[2*root+1].tag*(tree[2*root+1].right-tree[2*root+1].left+1);
    
59. }
    
60. long long findout(int start,int end,int root)
    
61. {
    
62.     if (tree[root].left==start&&tree[root].right==end)
    
63.     {
    
64.         return tree[root].sum+tree[root].tag*(end-start+1);
    
65.     }
    
66.     long long answer=0;
    
67.     tree[2*root].tag+=tree[root].tag;
    
68.     tree[2*root+1].tag+=tree[root].tag;
    
69.     tree[root].tag=0;
    
70.     tree[root].sum=tree[2*root].sum+tree[2*root+1].sum+tree[2*root].tag*(tree[2*root].right-tree[2*root].left+1)+tree[2*root+1].tag*(tree[2*root+1].right-tree[2*root+1].left+1);
    
71.     if(start>=tree[root*2+1].left)
    
72.     {
    
73.         answer=findout(start,end,root*2+1);
    
74.     }
    
75.     else
    
76.     {
    
77.         if(end<=tree[root*2].right)
    
78.         {
    
79.             answer=findout(start,end,root*2);
    
80.         }
    
81.         else
    
82.         {
    
83.             answer+=findout(start,tree[root*2].right,root*2);
    
84.             answer+=findout(tree[root*2+1].left,end,root*2+1);
    
85.         }
    
86.     }
    
87.     return answer;
    
88. }
    
89. signed main()
    
90. {
    
91.     scanf("%lld%lld",&n,&m);
    
92.     for(int i=1;i<=n;i++)
    
93.     {
    
94.         scanf("%lld",&a[i]);
    
95.     }
    
96.     setup(1,1,n);
    
97.     for(int i=1;i<=m;i++)
    
98.     {
    
99.         scanf("%lld",&k);
    
100.         if(k==1)
     
101.         {
     
102.             scanf("%lld%lld%lld",&l,&r,&x);
     
103.             add(l,r,1,x);
     
104.         }
     
105.         else
     
106.         {
     
107.             if(k==2)
     
108.             {
     
109.                 scanf("%lld%lld",&l,&r);
     
110.                 printf("%lld\n",findout(l,r,1));
     
111.             }
     
112.         }
     
113.     }
     
114.     return 0;
     
115. }

复制代码

walk_alone

1. #include <cstdio>
   
2. long long a[1000001],sum[4000001],tag[4000001];
   
3. void build(long long place,long long left,long long right)
   
4. {
   
5.     if(left==right)
   
6.     {
   
7.         sum[place]=a[left];
   
8.         return;
   
9.     }
   
10.     long long mid=(left+right)>>1;
    
11.     build(place<<1,left,mid);
    
12.     build(place<<1|1,mid+1,right);
    
13.     sum[place]=sum[place<<1]+sum[place<<1|1];
    
14. }
    
15. inline void find(long long left,long long right,long long place,long long x)
    
16. {
    
17.     tag[place]+=x;
    
18.     sum[place]+=x*(right-left+1);
    
19. }
    
20. inline void putdown(long long left,long long right,long long place)
    
21. {
    
22.     long long mid=(left+right)>>1;
    
23.     find(left,mid,place<<1,tag[place]);
    
24.     find(mid+1,right,place<<1|1,tag[place]);
    
25.     tag[place]=0;
    
26. }
    
27. inline void change(long long start,long long end,long long left,long long right,long long place,long long x)
    
28. {
    
29.     if(start<=left && right<=end)
    
30.     {
    
31.         tag[place]+=x;
    
32.         sum[place]+=x*(right-left+1);
    
33.         return;
    
34.     }   
    
35.     putdown(left,right,place);
    
36.     long long mid=(left+right)>>1;
    
37.     if(start<=mid)
    
38.         change(start,end,left,mid,place<<1,x);
    
39.     if(end>mid)
    
40.         change(start,end,mid+1,right,place<<1|1,x);
    
41.     sum[place]=sum[place<<1|1]+sum[place<<1];
    
42. }
    
43. long long query(long long start,long long end,long long left,long long right,long long place)
    
44. {
    
45.     long long ans=0;
    
46.     if(start<=left && right<=end)
    
47.         return ans=sum[place];
    
48.     long long mid=(left+right)>>1;
    
49.     putdown(left,right,place);
    
50.     if(start<=mid)
    
51.         ans+=query(start,end,left,mid,place<<1);
    
52.     if(end>mid)
    
53.         ans+=query(start,end,mid+1,right,place<<1|1);
    
54.     return ans;
    
55. }
    
56. int main()
    
57. {
    
58.     long long n,m,p,q,x;
    
59.     int k;
    
60.     scanf("%lld%lld",&n,&m);
    
61.     for(int i=1;i<=n;i++)
    
62.         scanf("%lld",&a[i]);
    
63.     build(1,1,n);
    
64.     for(int i=1;i<=m;i++)
    
65.     {
    
66.         scanf("%d",&k);
    
67.         if(k==1)
    
68.         {
    
69.             scanf("%lld%lld%lld",&p,&q,&x);
    
70.             change(p,q,1,n,1,x);
    
71.         }
    
72. 
    
73.         if(k==2)
    
74.         {
    
75.             scanf("%lld%lld",&p,&q);
    
76.             printf("%lld\n",query(p,q,1,n,1));
    
77.         }
    
78.     }
    
79.     return 0;
    
80. }

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. const int N = 2e5 + 10;
    
14. typedef long long LL;
    
15. LL sum[N * 4]= {0}, tag[N * 4]= {0},a[N];
    
16. void build(int l, int r, int o)
    
17. {
    
18.         if(l == r)
    
19.         {
    
20.                 sum[o] = a[l];
    
21.                 tag[o] = 0;
    
22.                 return ;
    
23.         }
    
24.         int mid = (l + r) >> 1;
    
25.         build(l, mid, o * 2);
    
26.         build(mid + 1, r, o << 1 | 1);
    
27.         sum[o] = sum[o << 1] + sum[o << 1 | 1];
    
28.         tag[o] = 0;
    
29.         return ;
    
30. }
    
31. void update(int L, int R, LL add, int l, int r, int o)
    
32. {
    
33.         if(L <= l && r <= R)
    
34.         {
    
35.                 sum[o] += (r - l + 1) * add;
    
36.                 tag[o] += add;
    
37.                 return ;
    
38.         }
    
39.         int mid = (l + r) >> 1;
    
40.         if(tag[o])
    
41.         {
    
42.                 sum[o << 1] += tag[o] * (mid - l + 1);
    
43.                 tag[o << 1] += tag[o];
    
44.                 sum[o << 1|1] += tag[o] * (r - mid);
    
45.                 tag[o << 1|1] += tag[o];
    
46.                 tag[o] = 0;
    
47.         }
    
48.         if(L <= mid) update(L, R, add, l, mid, o << 1);
    
49.         if(R > mid) update(L, R, add, mid + 1, r, o << 1 | 1);
    
50.         sum[o] = sum[o << 1] + sum[o << 1 | 1];
    
51. }
    
52. LL query(int L, int R, int l, int r, int o)
    
53. {
    
54.         if(L <= l && r <= R)
    
55.         {
    
56.                 return sum[o];
    
57.         }
    
58.         int mid = (l + r) >> 1;
    
59.         if(tag[o])
    
60.         {
    
61.                 sum[o << 1] += tag[o] * (mid - l + 1);
    
62.                 tag[o << 1] += tag[o];
    
63.                 sum[o << 1|1] += tag[o] * (r - mid);
    
64.                 tag[o << 1|1] += tag[o];
    
65.                 tag[o] = 0;
    
66.         }
    
67.         LL ans = 0;
    
68.         if(L <= mid) ans += query(L, R, l, mid, o << 1);
    
69.         if(R > mid) ans += query(L, R, mid + 1, r, o << 1 | 1);
    
70.         return ans;
    
71. }
    
72. 
    
73. int main()
    
74. {
    
75.         int n, m;
    
76.         scanf("%d %d", &n, &m);
    
77.         for(int i=1; i<=n; i++)
    
78.                 scanf("%lld", &a[i]);
    
79.         build(1, n, 1);
    
80.         while(m --)
    
81.         {
    
82.                 int op;
    
83.                 scanf("%d", &op);
    
84.                 if(op == 1)
    
85.                 {
    
86.                         int l, r;
    
87.                         LL x;
    
88.                         scanf("%d %d %lld", &l, &r, &x);
    
89.                         update(l, r, x, 1, n, 1);
    
90.                 }
    
91.                 else
    
92.                 {
    
93.                         int l, r;
    
94.                         scanf("%d %d", &l, &r);
    
95.                         printf("%lld\n", query(l, r, 1, n, 1));
    
96.                 }
    
97.         }
    
98. }

复制代码

liubo

1. #include<iostream>
   
2. using namespace std;
   
3. struct node{
   
4.     int l,r;
   
5.     long long sum;
   
6.     long long inc;
   
7.     int mid(){
   
8.         return (l + r)/2;
   
9.     }
   
10. }t[300010];
    
11. void buildTree(int root,int l,int r){
    
12.     node &n = t[root];
    
13.     n.l = l;
    
14.     n.r = r;
    
15.     n.sum = 0;
    
16.     n.inc = 0;
    
17.     /**!!!**/if(l == r) return;
    
18.     buildTree(root * 2 + 1,l,n.mid());
    
19.     buildTree(root * 2 + 2,n.mid() + 1,r);
    
20. }
    
21. void insertNum(int root,int i,int v){
    
22.     node &n = t[root];
    
23.     if(n.l == n.r && n.l == i){
    
24.         n.sum = v;
    
25.         return;
    
26.     }
    
27.     n.sum += v;
    
28.     if(i > n.mid())
    
29.         insertNum(root * 2 + 2,i,v);
    
30.     else
    
31.         insertNum(root * 2 + 1,i,v);
    
32. }
    
33. void addNum(int root,int l,int r,int v){
    
34.     node &n = t[root];
    
35.     if(n.l == l && n.r == r){
    
36.         n.inc += v;
    
37.         return;
    
38.     }
    
39.     //n.inc += v;
    
40.     n.sum += v * (r - l + 1);
    
41.     if(l > n.mid())
    
42.         addNum(root * 2 + 2,l,r,v);
    
43.     else if(r <= n.mid())
    
44.         addNum(root * 2 + 1,l,r,v);
    
45.     else{
    
46.         addNum(root * 2 + 1,l,n.mid(),v);
    
47.         addNum(root * 2 + 2,n.mid() + 1,r,v);
    
48.     }
    
49. }
    
50. long long askSum(int root,int l,int r){
    
51.     node &n = t[root];
    
52.     if(n.l == l && n.r == r)
    
53.         return n.sum + (r - l + 1) * n.inc;
    
54.     n.sum += (n.r - n.l + 1) * n.inc;
    
55.     addNum(root * 2 + 1,n.l,n.mid(),n.inc);
    
56.     addNum(root * 2 + 2,n.mid() + 1,n.r,n.inc);
    
57.     n.inc = 0;
    
58. 
    
59.     if(l > n.mid())
    
60.         return askSum(root * 2 + 2,l,r);
    
61.     else if(r <= n.mid())
    
62.         return askSum(root * 2 + 1,l,r);
    
63.     else{
    
64.         return askSum(root * 2 + 1,l,n.mid()) +
    
65.         askSum(root * 2 + 2,n.mid() + 1,r);
    
66.     }
    
67. }
    
68. int main(){
    
69.     int n,m,c,l,r,v,k;
    
70.     cin >> n >> m;
    
71.     buildTree(0,1,n);
    
72.     for(int i = 1;i <= n;i++){
    
73.         cin >> k;
    
74.         insertNum(0,i,k);
    
75.     }
    
76.     for(int i = 1;i <= m;i++){
    
77.         cin >> c;
    
78.         if(c == 1){
    
79.             cin >> l >> r >> k;
    
80.             addNum(0,l,r,k);
    
81.         }else{
    
82.             cin >> l >> r;
    
83.             cout << askSum(0,l,r) << endl;
    
84.         }
    
85.     }
    
86.     return 0;
    
87. }

复制代码