Codevs1082 线段树练习 3

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，

再接下来一个正整数Q，每行表示操作的个数，

如果第一个数是1，后接3个正整数，

表示在区间[a,b]内每个数增加X,如果是2，

表示操作2询问区间[a,b]的和是多少。

pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

1 2 3 2

2 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

树状数组40分（剩下超时）：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 int f[200001];
 8 
 9 int read()
10 {
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 
17 int lowbit(int x)
18 {
19     return x&(-x);
20 }
21 
22 void update(int x,int num)
23 {
24     while(x<=n)
25     {
26         f[x]+=num;
27         x+=lowbit(x);
28     }
29 }
30 
31 int sum(int x)
32 {
33     int sum=0;
34     while(x>0)
35     {
36         sum+=f[x];
37         x-=lowbit(x);
38     }
39     return sum;
40 }
41 
42 int main()
43 {
44     n=read();
45     for(int i=1;i<=n;i++)
46         update(i,read());
47     m=read();
48     for(int i=1;i<=m;i++)
49     {
50         int t=read(),x,y,z;
51         if(t==1)
52         {
53             x=read();y=read();z=read();
54             for(int j=x;j<=y;j++)
55                 update(j,z);
56         }
57         if(t==2)
58         {
59             x=read();y=read();
60             printf("%d
",sum(y)-sum(x-1));
61         }
62     }
63     return 0;
64 }

线段树：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 
  6 struct node
  7 {
  8     int left,right,flag;
  9     long long sum;
 10 }tree[600000];
 11 
 12 int n,q;
 13 int a[200001];
 14 
 15 int read()
 16 {
 17     int x=0,f=1;char ch=getchar();
 18     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
 19     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 20     return x*f;
 21 }
 22 
 23 void build(int node,int left,int right)
 24 {
 25     tree[node].left=left;tree[node].right=right;
 26     if(left==right)
 27     {
 28         tree[node].sum=a[left];
 29         return;
 30     }
 31     int mid=(left+right)>>1;
 32     build(node<<1,left,mid);
 33     build(node<<1|1,mid+1,right);
 34     tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
 35 }
 36 
 37 void pushdown(int node)
 38 {
 39     int x=tree[node].right-tree[node].left+1;
 40     tree[node<<1].flag+=tree[node].flag;
 41     tree[node<<1|1].flag+=tree[node].flag;
 42     tree[node<<1].sum+=(x-(x>>1))*tree[node].flag;
 43     tree[node<<1|1].sum+=(x>>1)*tree[node].flag;
 44     tree[node].flag=0;
 45 }
 46 
 47 void update(int node,int left,int right,int x)
 48 {
 49     int mid=(tree[node].left+tree[node].right)>>1;
 50     tree[node].sum+=(right-left+1)*x;
 51     if(tree[node].left==left&&tree[node].right==right)
 52     {
 53         tree[node].flag+=x;
 54         return;
 55     }
 56     if(tree[node].left==tree[node].right) return;
 57     if(tree[node].flag>0) pushdown(node);
 58     if(right<=mid) update(node<<1,left,right,x);
 59     else if(left>mid) update(node<<1|1,left,right,x);
 60     else
 61     {
 62         update(node<<1,left,mid,x);
 63         update(node<<1|1,mid+1,right,x);
 64     }
 65     tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
 66 }
 67 
 68 long long query(int node,int left,int right)
 69 {
 70     int mid=(tree[node].left+tree[node].right)>>1;
 71     if(tree[node].left==left&&tree[node].right==right)
 72         return tree[node].sum;
 73     if(tree[node].flag>0) pushdown(node);
 74     if(right<=mid)
 75         return     query(node<<1,left,right);
 76     else if(left>mid)
 77         return query(node<<1|1,left,right);
 78     else
 79         return query(node<<1,left,mid)+query(node<<1|1,mid+1,right);
 80 }
 81 
 82 int main()
 83 {
 84     n=read();
 85     for(int i=1;i<=n;i++)
 86         a[i]=read();
 87     build(1,1,n);
 88     q=read();
 89     for(int i=1;i<=q;i++)
 90     {
 91         int t=read(),a=read(),b=read(),x;
 92         if(t==1)
 93         {
 94             x=read();
 95             update(1,a,b,x);
 96         }
 97         if(t==2)
 98         {
 99             cout<<query(1,a,b)<<endl;
100         }
101     }
102     return 0;
103 }