线段树（单点更新and成段更新）

线段树需要的空间。

区间为1-->n

假设是一棵完全二叉树，且树高为i。

完全二叉树性质：第i层最多有2^(i-1)个结点。

那么 2^(i-1) = n; i = log2(n) + 1;

共有 2^i - 1 个结点，即 2^(log2(n) + 1) - 1个结点

即2 * 2^log2(n) - 1 = 2 * n - 1

但这是建立树是完全二叉树的情况下。

但是如图所示，树可能不是完全二叉树，最下面一层的结点个数>n, 我们以2n来来计算，那么就需要4*n-1的空间。

http://acm.hdu.edu.cn/showproblem.php?pid=1166

单点更新

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 50000;
 4 int a[N*4],ans;
 5 void swap(int &a, int &b)
 6 {
 7     int t = a;
 8     a = b;
 9     b = t;
10 }
11 void build(int rt, int l, int r)
12 {
13     if(l==r)
14     {
15         scanf("%d",&a[rt]);
16         return;
17     }
18     int mid = (l + r) >> 1;
19     build(rt<<1,l,mid);
20     build(rt<<1|1,mid+1,r);
21     a[rt] = a[rt<<1] + a[rt<<1|1];
22 }
23 
24 void query(int rt, int L, int R, int l, int r)
25 {
26     if(L==l && R==r)
27     {
28         ans += a[rt];
29         return;
30     }
31     int mid = (l + r) >> 1;
32     if(R<=mid)
33         query(rt<<1,L,R,l,mid);
34     else if(L>mid)
35         query(rt<<1|1,L,R,mid+1,r);
36     else
37     {
38         query(rt<<1,L,mid,l,mid);
39         query(rt<<1|1,mid+1,R,mid+1,r);
40     }
41 }
42 void update(int rt, int val, int pos, int l, int r)
43 {
44     if(l == r)
45     {
46         a[rt] += val;
47         return ;
48     }    
49     int mid = (l + r) >> 1;
50     if(pos <= mid)
51         update(rt<<1,val,pos,l,mid);
52     else
53         update(rt<<1|1,val,pos,mid+1,r);
54     a[rt] = a[rt<<1] + a[rt<<1|1];
55 }
56 int main()
57 {
58     int t,n,i,j,tCase;
59     char str[10];
60     scanf("%d",&t);
61     for(tCase=1; tCase<=t; ++tCase)
62     {
63         memset(a,0,sizeof(a));
64         scanf("%d",&n);
65         build(1,1,n);
66         printf("Case %d:
",tCase);
67         while(true)
68         {
69             scanf("%s",str);
70             if(str[0]=='E')
71                 break;
72             scanf("%d%d",&i,&j);
73             if(str[0]=='Q')
74             {
75                 ans = 0;
76                 if(i > j)
77                     swap(i,j);
78                 query(1,i,j,1,n);
79                 printf("%d
",ans);
80             }
81             else if(str[0]=='A')
82             {
83                 update(1,j,i,1,n);
84             }
85             else
86                 update(1,-j,i,1,n);
87         }
88     }
89     return 0;
90 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=1698

成段更新，要用到懒惰标记，每次更改区间时，不会更新到叶子结点，而是标记，等有需要了才去更新

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 100000 + 10;
 4 struct node
 5 {
 6     int sum;
 7     int tag;
 8 }a[N*8];
 9 void pushUp(int rt)
10 {
11     a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum;
12 }
13 void pushDown(int rt, int m)
14 {
15     if(a[rt].tag != 0)
16     {
17         a[rt<<1].tag = a[rt<<1|1].tag = a[rt].tag;
18         a[rt<<1].sum = (m-(m>>1)) * a[rt].tag;
19         a[rt<<1|1].sum = (m>>1) * a[rt].tag;
20         a[rt].tag = 0;
21     }
22 }
23 void build(int rt, int l, int r)
24 {
25     a[rt].tag = 0;
26     if(l==r)
27     {
28         a[rt].sum = 1;
29         return ;
30     }
31     int mid = (l + r) >> 1;
32     build(rt<<1,l,mid);
33     build(rt<<1|1,mid+1,r);
34     pushUp(rt);
35 }
36 void update(int rt, int L, int R, int val, int l, int r)
37 {
38     if(L<=l && r<=R)
39     {
40         a[rt].sum = (r-l+1)*val;
41         a[rt].tag = val;
42         return;
43     }
44     pushDown(rt,r-l+1);
45     int mid = (l + r) >> 1;
46     if(L<=mid) update(rt<<1,L,R,val,l,mid);
47     if(R>mid) update(rt<<1|1,L,R,val,mid+1,r);
48     pushUp(rt);
49 }
50 
51 
52 int main()
53 {
54     int t,tCase,n,i,x,y,z,q;
55     scanf("%d",&t);
56     for(tCase=1; tCase<=t; ++tCase)
57     {
58         scanf("%d",&n);
59         build(1,1,n);
60         scanf("%d",&q);
61         for(i=0; i<q; ++i)
62         {
63             scanf("%d%d%d",&x,&y,&z);
64             update(1,x,y,z,1,n);
65         }
66         printf("Case %d: The total value of the hook is %d.
",tCase,a[1].sum);
67     }
68     return 0;
69 }

View Code