codevs 1080 线段树练习

链接：http://codevs.cn/problem/1080/

先用树状数组水一发，再用线段树水一发

树状数组代码：84ms

 1 #include<cstdio>  
 2 #include<iostream>  
 3 #include<algorithm>
 4 #include<math.h> 
 5 #include<string.h>  
 6 #include<vector> 
 7 #include<queue>
 8 #include<iterator>
 9 #include<vector>
10 #include<set>
11 #define dinf 0x3f3f3f3f
12 typedef long long ll;
13 const int Max=(1<<16)+10;
14 using namespace std;
15 
16 #define SIZE 1000005
17 
18 int c[SIZE],a[SIZE];
19 
20 int Lowbit(int x)
21 {
22     return x&(-x);
23 }
24 
25 int Sum(int x)
26 {
27     int sum=0;
28     while(x>0)
29     {
30         sum+=c[x];
31         x-=Lowbit(x);
32     }
33     return sum;
34 }
35 
36 void Update(int i,int x)
37 {
38     while(i<=SIZE)//要把所有的与i相关的c数组中的值全部更新，不然会出错 
39     {
40         c[i]+=x;
41         i+=Lowbit(i);
42     }
43 }
44 
45 
46 int main()
47 {
48     int n,m; 
49     while(~scanf("%d",&n))
50     {
51         memset(a,0,sizeof(a));
52         memset(c,0,sizeof(c));
53         
54         for(int i=1;i<=n;i++)
55         {
56             scanf("%d",&a[i]);
57             Update(i,a[i]);
58         }
59         scanf("%d",&m);
60         int op,node,num;
61         for(int i=1;i<=m;i++)
62         {
63             scanf("%d %d %d",&op,&node,&num);
64             if(op==1)
65                 Update(node,num);
66             else if(op==2)
67             {
68                 printf("%d
",Sum(num)-Sum(node-1));
69             }
70         }
71     } 
72     return 0;
73  }

线段树代码：48ms

 1 #include<cstdio>
 2 using namespace std;
 3 struct RE
 4 {
 5       int sum,l,r;
 6 }tree[400001];
 7 int a[100001];
 8 void build(int node,int l,int r)
 9 {
10       int mid=(l+r)>>1;
11     tree[node].l=l;
12       tree[node].r=r;
13       if (l==r)
14       {
15             tree[node].sum=a[l];
16             return;
17     }
18       build(2*node,l,mid);
19       build(2*node+1,mid+1,r);
20       tree[node].sum+=tree[2*node].sum+tree[2*node+1].sum;
21 }
22 void updata(int node,int a,int b)
23 {
24       int mid=(tree[node].l+tree[node].r)>>1;
25       if (mid==tree[node].l&&mid==tree[node].r)
26       {
27             tree[node].sum+=b;
28             return;
29     }
30     if (a<=mid) 
31         updata(2*node,a,b);
32     else 
33         updata(2*node+1,a,b);
34     tree[node].sum+=b;
35 }
36 int query(int node,int l,int r)
37 {
38       int mid=(tree[node].l+tree[node].r)>>1;
39       if (tree[node].l==l&&tree[node].r==r)
40           return tree[node].sum;
41       if (l>mid) 
42           return query(2*node+1,l,r);
43       if (r<=mid) 
44           return query(2*node,l,r);
45       return query(2*node,l,mid)+query(2*node+1,mid+1,r);
46 }
47 int main()
48 {
49       int n,m;
50       scanf("%d",&n);
51       int i,j;
52       for (i=1;i<=n;i++)
53           scanf("%d",&a[i]);
54       build(1,1,n);
55       scanf("%d",&m);
56       int sign,a,b;
57       for (i=1;i<=m;i++)
58       {
59             scanf("%d%d%d",&sign,&a,&b);
60             if (sign==1) updata(1,a,b);
61             else printf("%d
",query(1,a,b));
62     }
63     return 0;
64 }