线段树

线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!

性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍

证明线段树需要的空间为数组大小的四倍：

设根区间为[1,n]，根据二叉树的性质：

　　1，二叉树的总节点数N=N0+N1+N2

　　2，N=二叉树的总度数+1=0×N0+1×N1+2×N2

又有线段树的N1=0，N0=n，N2=N0+1=n+1

可得线段树的总节点数N=2×n+1

若采用数组来存放，则根据二叉树的性质：

　　3，节点数为N的完全二叉树，树的高度为（log₂n）+1

　　4，高度为h的二叉树最多有2^h-1个节点

又线段树是一颗完全二叉树

可得数组的最大长度应为2^(（log₂n）+1)-1=4n-1

1.单点更新，区间求和，例题：HDU 1166

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 const int N=50000+11;
 6 int a[N<<2];
 7 void getdown(int rt)
 8 {
 9     a[rt]=a[rt<<1]+a[rt<<1|1];
10 }
11 void build(int l,int r,int rt)
12 {
13     if(l==r)
14     {
15         scanf("%d",&a[rt]);
16         return ;
17     }
18     int mid=(l+r)>>1;
19     build(lson);
20     build(rson);
21     getdown(rt);
22 }
23 void updata(int p,int x,int l,int r,int rt)
24 {
25     if(l==r)
26     {
27         a[rt]+=x;
28         return ;
29     }
30     int mid=(l+r)>>1;
31     if(p<=mid)    updata(p,x,lson);
32     else        updata(p,x,rson);
33     getdown(rt);
34 }
35 int Q(int L,int R,int l,int r,int rt)
36 {
37     if(L<=l&&R>=r)    return a[rt];
38     int ans=0;
39     int mid=(l+r)>>1;
40     if(L<=mid)    ans+=Q(L,R,lson);
41     if(R>mid)    ans+=Q(L,R,rson);
42     return ans;
43 }
44 int main()
45 {
46     int t,cas=0,n;
47     scanf("%d",&t);
48     while(t--)
49     {
50         scanf("%d",&n);
51         build(1,n,1);
52         char s[10];int x,y;
53         printf("Case %d:
",++cas);
54         while(scanf("%s",s)&&s[0]!='E')
55         {
56             scanf("%d%d",&x,&y);
57             if(s[0]=='Q')    printf("%d
",Q(x,y,1,n,1));
58             if(s[0]=='A')    updata(x,y,1,n,1);
59             if(s[0]=='S')    updata(x,-y,1,n,1);
60         }
61     }
62     return 0;
63 }

View Code

2.区间更新，区间求和，例题：POJ 3468

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 typedef long long ll;
 6 const int N=1e5+11;
 7 ll add[N<<2],sum[N<<2];
 8 void Pushup(int rt)
 9 {
10     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
11 }
12 void Pushdown(int rt,int d)
13 {
14     if(add[rt])
15     {
16         add[rt<<1]+=add[rt];
17         add[rt<<1|1]+=add[rt];
18         sum[rt<<1]+=add[rt]*(d-(d>>1));
19         sum[rt<<1|1]+=add[rt]*(d>>1);
20         add[rt]=0;
21     }
22 }
23 void build(int l,int r,int rt)
24 {
25     add[rt]=0;
26     if(l==r)
27     {
28         scanf("%I64d",&sum[rt]);
29         return ;
30     }
31     int mid=(l+r)>>1;
32     build(lson);build(rson);
33     Pushup(rt);
34 }
35 void updata(int L,int R,int x,int l,int r,int rt)
36 {
37     if(L<=l&&R>=r)
38     {
39         add[rt]+=x;
40         sum[rt]+=(ll)x*(r-l+1);
41         return ;
42     }
43     Pushdown(rt,r-l+1);
44     int mid=(l+r)>>1;
45     if(L<=mid)    updata(L,R,x,lson);
46     if(R>mid)    updata(L,R,x,rson);
47     Pushup(rt);
48 }
49 ll Q(int L,int R,int l,int r,int rt)
50 {
51     if(L<=l&&R>=r)
52         return sum[rt];
53     Pushdown(rt,r-l+1);
54     int mid=(l+r)>>1;
55     ll ans=0;
56     if(L<=mid)    ans+=Q(L,R,lson);
57     if(R>mid)    ans+=Q(L,R,rson);
58     return ans;
59 }
60 int main()
61 {
62     int n,m,x,y,z;
63     char op[2];
64     scanf("%d%d",&n,&m);
65      build(1,n,1);
66      while(m--)
67      {
68          scanf("%s",op);
69          if(op[0]=='C')
70          {
71              scanf("%d%d%d",&x,&y,&z);
72              updata(x,y,z,1,n,1);
73          }
74          else
75          {
76              scanf("%d%d",&x,&y);
77              printf("%I64d
",Q(x,y,1,n,1));
78          }
79      }
80     return 0;
81 }

View Code

参考文章：http://blog.csdn.net/metalseed/article/details/8039326