segment tree

　　线段树

基础讲解：

基础讲解2

学了一天线段树，写一点小感想：两种建树方式：开一个结构体，开一个数组，当然后者效率高

1:区间更新＋点合并（求层次）：求逆序数，求顺序数，通过下标离散化映射，因为不需要考虑区间的长度，只需要考虑每个数之间的位置关系。注意与hash数组－－映射的联合应用。

2.区间更新有几种版本注意 l,m m+1,r ,极具容易runtime error见了你的鬼了。

3.延时标记，用于区间更新＋区间合并每次用一个变量记录增量，当满足条件则更新，否则把增量传递给子节点，继续往下查找。

4.感觉用结构体建树以后会省很多事，只需要传递根节点就ok了，注意给的数的规律。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

学会映射，学会从整体抽象出个体，大大减少复杂度 map,hash映射

单点更新

成段更新

区间合并

扫描线

多棵线段树，区间不连续，但有一定规律间隔，用多棵树表示不同的偏移区间。

Poj,2352

一个坐标轴上有多颗星星，计算一个星星左下角的星星个数，也即为它的层次；

因为输入是按照y升序然后按x升序排，所以只需要考虑x轴坐标。

每次输入一个x，使(x,32000)的数层次加1，这样query(x)返回其层次，再用类hash返回其个数

线段树。。。。。。。。。。。今天第一次看，看了一上午，总算有点感觉了。。感觉就是build,query,update,pushup,pushdown,这几个模版函数改一些细节，然后用于更新某点，某连续线段，区间合并，扫描线等求并周长并面积。这道题就是一个区间更新的题目。。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 struct Node
 7 {
 8     int l,r,val;
 9 }tree[32000*4];
10 
11 void build(int l,int r,int rt)
12 {
13     tree[rt].l=l;
14     tree[rt].r=r;
15     tree[rt].val=0;
16     if(l==r)return;
17     
18     int m=(l+r)/2;
19     build(l,m,rt*2);
20     build(m+1,r,rt*2+1);
21 }
22 
23 void update(int l,int r,int rt,int val)
24 {
25     if(tree[rt].l==l && tree[rt].r==r)
26     {
27         tree[rt].val+=val;
28         return;
29     }
30     
31     int m=(tree[rt].l+tree[rt].r)/2;
32     
33     if(r<=m) update(l,r,rt*2,val);
34     else if(l>m) update(l,r,rt*2+1,val);
35     else
36     {
37         update(l,m,rt*2,val);
38         update(m+1,r,rt*2+1,val);
39     }
40 }
41 
42 int query(int x,int rt)
43 {
44     if(tree[rt].l==tree[rt].r)
45         return tree[rt].val;
46     
47     int m=(tree[rt].l+tree[rt].r)/2;
48     if(x<=m) return query(x,rt*2)+tree[rt].val;
49     else return query(x,rt*2+1)+tree[rt].val;
50 }
51 
52 int level[32000];
53 int main()
54 {
55     int N;
56     int x,y,i;
57     scanf("%d",&N);
58     build(0,32000,1);
59     for(i=0;i<N;i++)
60     {
61         scanf("%d%d",&x,&y);
62         ++level[query(x,1)];
63         update(x,32000,1,1);
64     }
65     for(i=0;i<N;i++)
66         printf("%d
",level[i]);
67     return 0;
68 }

View Code

poj,2299

求逆序数，归并排序最快

再一个就是用线段树，用pos纪录原来数据的位置，按从大到小排序，用其下标代替数据更新线段树，

例如: 5 9 1 0 5 4 对应的序号:1,2,3,4,5

9 5 4 1 0 对应的序号：1,4,5,2,3

然后按照 1-4-5-2-3插入，依次使a[i]-n的区间段加一，表示在a[i+1]之前有几个比他大的数

其实从小排到大，然后每次更新[0,a[i]]也是对的

－－－－－－－－其实我感觉我可以去巧过了，poj这题的测试数据给的有点水，当n特别大的时候，一定会越界

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <string>
 5 #define maxn 5000010
 6 #define ll long long
 7 using namespace std;
 8 
 9 struct Node
10 {
11     int l,r,cnt;
12     int val,pos;
13 }tree[maxn];
14 
15 bool cmp(Node x,Node y)
16 {
17     return x.val>y.val;
18 }
19 
20 void build(int l,int r,int rt)
21 {
22     tree[rt].l=l;
23     tree[rt].r=r;
24     tree[rt].cnt=0;
25     
26     if(l==r) return;
27     int m=(l+r)/2;
28     build(l,m,rt*2);
29     build(m+1,r,rt*2+1);
30 }
31 
32 void update(int l,int r,int rt,int val)
33 {
34     if(tree[rt].l==l && tree[rt].r==r)
35     {
36         tree[rt].cnt+=val;
37         return;
38     }
39     
40     int m=(tree[rt].l+tree[rt].r)/2;
41     
42     if(r<=m) update(l,r,rt*2,val);
43     else if(l>m) update(l,r,rt*2+1,val);
44     else
45     {
46         update(l,m,rt*2,val);
47         update(m+1,r,rt*2+1,val);
48     }
49 }
50 
51 int query(int x,int rt)
52 {
53     if(tree[rt].l==tree[rt].r)
54         return tree[rt].cnt;
55     int m=(tree[rt].l+tree[rt].r)/2;
56     
57     if(x<=m) return query(x,rt*2)+tree[rt].cnt;
58     else return query(x,rt*2+1)+tree[rt].cnt;
59 }
60 
61 int main()
62 {
63     int n;
64     int i;
65     ll ans;
66     while(scanf("%d",&n),n)
67     {
68         ans=0;
69         for(i=0;i<n;i++)
70         {
71             scanf("%d",&tree[i].val);
72             tree[i].pos=i+1;
73         }
74         sort(tree,tree+n,cmp);
75         build(1,n,1);
76         
77         for(i=0;i<n;i++)
78         {
79             ans+=query(tree[i].pos,1);
80             update(tree[i].pos,n,1,1);
81         }
82         
83         printf("%lld
",ans);
84     }
85     return 0;
86 }

View Code

重写了，保证了不会越界。。时间也要短1/3

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <string>
 5 
 6 #define maxn 5000010
 7 typedef long long ll;
 8 
 9 using namespace std;
10 struct Node
11 {
12     int val,pos;
13 }a[maxn];
14 
15 bool cmp(Node a,Node b)
16 {
17     return a.val>b.val;
18 }
19 
20 int sum[maxn<<2];
21 
22 
23 void build(int rt,int l,int r)
24 {
25     sum[rt]=0;
26     if(l==r) return;
27     
28     int m=(l+r)>>1;
29     build(rt<<1,l,m);
30     build(rt<<1|1,m+1,r);
31 }
32 
33 void update(int rt,int l,int r,int x)
34 {
35     sum[rt]+=1;
36     
37     if(l==r)return;
38     
39     int m=(l+r)>>1;
40     if(x<=m) update(rt<<1,l,m,x);
41     else update(rt<<1|1,m+1,r,x);
42 }
43 
44 int query(int rt,int l,int r,int L,int R)
45 {
46     if(L==l && R==r)
47         return sum[rt];
48     
49     int m=(l+r)>>1;
50     
51     if(R<=m) return query(rt<<1,l,m,L,R);
52     else if(L>m) return query(rt<<1|1,m+1,r,L,R);
53     else
54         return query(rt<<1,l,m,L,m)+query(rt<<1|1,m+1,r,m+1,R);
55 }
56 
57 int main()
58 {
59     int n;
60     ll ans;
61     while(scanf("%d",&n),n)
62     {
63         for(int i=0;i<n;i++)
64         {
65             scanf("%d",&a[i].val);
66             a[i].pos=i+1;
67         }
68         sort(a,a+n,cmp);
69         ans=0;
70         build(1,1,n);
71         for(int i=0;i<n;i++)
72         {
73             ans+=query(1,1,n,1,a[i].pos);
74             update(1,1,n,a[i].pos);
75         }
76         printf("%lld
",ans);
77         
78     }
79     return 0;
80 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #define LL long long
 5 #define lson l,m,rt<<1
 6 #define rson m+1,r,rt<<1|1
 7 
 8 using namespace std;
 9 const int maxn=500010;
10 int col[maxn<<2];
11 
12 struct Node
13 {
14     int val,pos;
15 }q[maxn];
16 
17 bool cmp(Node x,Node y)
18 {
19     return x.val>y.val;
20 }
21 void build(int l,int r,int rt)
22 {
23     col[rt]=0;
24     
25     if(l==r) return;
26     int m=(l+r)>>1;
27     
28     build(lson);
29     build(rson);
30 }
31 
32 void update(int L,int R,int l,int r,int rt,int c)
33 {
34     if(L<=l && r<=R)
35     {
36         col[rt]+=c;
37         return;
38     }
39     
40     int m=(l+r)>>1;
41     
42     if(L<=m) update(L,R,lson,c);
43     if(R>m) update(L,R,rson,c);
44 }
45 
46 LL query(int x,int l,int r,int rt)
47 {
48     if(l==r)
49         return col[rt];
50     
51     int m=(l+r)>>1;
52     
53     if(x<=m) return query(x,lson)+col[rt];
54     else return query(x,rson)+col[rt];
55     
56 }
57 
58 int main()
59 {
60     int n;
61     while(scanf("%d",&n),n)
62     {
63         for(int i=0;i<n;i++)
64         {
65             scanf("%d",&q[i].val);
66             q[i].pos=i+1;
67         }
68         
69         sort(q,q+n,cmp);
70         
71         LL ans=0;
72         build(1,n,1);
73         for(int i=0;i<n;i++)
74         {
75             ans+=query(q[i].pos,1,n,1);
76             update(q[i].pos,n,1,n,1,1);
77         }
78         printf("%lld
",ans);
79     }
80     return 0;
81 }

这份代码比前两份易懂，与第一题差不多

poj,3468

合并区间和成段更新区间的题目，线段树模版题。。。

好的代码让人情不自禁多打几遍～～～～～－－！

延时标记，每次只更新其子节点，大大提高效率，普通线段树就会tle，向上向下传递精髓～～～～

 1 #include <iostream>
 2 #include <cstdio>
 3 #define lson l,m,rt<<1
 4 #define rson m+1,r,rt<<1|1
 5 #define root 1,N,1
 6 #define LL long long
 7 
 8 using namespace std;
 9 const int maxn=100010;
10 LL add[maxn<<2];
11 LL sum[maxn<<2];
12 
13 void PushUp(int rt)
14 {
15     sum[rt]=sum[rt<<1]+sum[rt<<1|1];  //值向上传递
16 }
17 
18 void PushDown(int rt,int m)
19 {
20     if(add[rt])  //值向下传递，即延时标记，大大提高效率
21     {
22         add[rt<<1]+=add[rt];  //增量传递
23         add[rt<<1|1]+=add[rt];
24         sum[rt<<1]+=add[rt]*(m-(m>>1));  //线段区间传递
25         sum[rt<<1|1]+=add[rt]*(m>>1);
26         add[rt]=0;
27     }
28 }
29 
30 void build(int l,int r,int rt)
31 {
32     add[rt]=0;   //记录每一层的增量即c
33     if(l==r)
34     {
35         scanf("%lld",&sum[rt]);
36         return;
37     }
38     int m=(l+r)>>1;
39     
40     build(lson);
41     build(rson);
42     PushUp(rt);
43 }
44 
45 void update(int L,int R,int c,int l,int r,int rt)
46 {
47     if(L<=l && r<=R)  //(1)
48     {
49         add[rt]+=c;
50         sum[rt]+=(LL)c*(r-l+1);
51         return;
52     }
53     
54     PushDown(rt,r-l+1);   //用于一个增量c来标记，判断(1)是否满足，如不满足则把增量传给子节点，考察他的子节点
55     int m=(l+r)>>1;       //每次就更新子节点就可以了，不需要更新全部的节点,等到满足条件然后再使其线段增长
56     
57     if(L<=m) update(L,R,c,lson);
58     if(R>m) update(L,R,c,rson);
59     PushUp(rt);    //更新子节点，向上传递更新根节点
60 }
61 
62 LL query(int L,int R,int l,int r,int rt)
63 {
64     if(L<=l && r<=R)
65         return sum[rt];
66     
67     int m=(l+r)>>1;
68     PushDown(rt,r-l+1);    //sum[rt]每次记录的是根节点的值，然后向下更新其子节点的值为下一次访问所使用
69     LL ret=0;
70     if(L<=m) ret+=query(L,R,lson);
71     if(R>m) ret+=query(L,R,rson);
72     return ret;
73 }
74 
75 int main()
76 {
77     int N,Q;
78     scanf("%d%d",&N,&Q);
79     build(root);
80     int a,b,c;
81     while(Q--)
82     {
83         char op[2];
84         scanf("%s",op);
85         if(op[0]=='Q')
86         {
87             scanf("%d%d",&a,&b);
88             printf("%lld
",query(a,b,root));
89         }
90         else
91         {
92             scanf("%d%d%d",&a,&b,&c);
93             update(a,b,c,root);
94         }
95     }
96     return 0;
97 }

重写了

参考：http://blog.csdn.net/scnu_jiechao/article/details/8576202

poj,2528

因为数据弱了，老是wa～

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 using namespace std;
  6 #define lson l,m,rt<<1
  7 #define rson m+1,r,rt<<1|1
  8 
  9 
 10 const int maxn=11111;
 11 
 12 bool hash[maxn];
 13 int col[maxn<<4];
 14 int li[maxn],ri[maxn];
 15 int X[maxn*3];
 16 int cnt;
 17 
 18 void PushDown(int rt)
 19 {
 20         col[rt<<1]=col[rt<<1|1]=col[rt];  //向下传递，即覆盖，例如 当1-3的海报先贴，再贴1-4的海报，1-3就会被会被覆盖，不算在内
 21         col[rt]=-1;
 22 }
 23 
 24 
 25 void update(int L,int R,int c,int l,int r,int rt)
 26 {
 27     if(L<=l && r<=R)
 28     {
 29         col[rt]=c;   //也充当延时标记，一层层传递，
 30         return;
 31     }
 32     if(col[rt]!=-1) PushDown(rt);
 33     int m=(l+r)>>1;
 34     
 35     if(L<=m) update(L,R,c,lson);
 36     if(R>m) update(L,R,c,rson);
 37 }
 38 
 39 void query(int l,int r,int rt)
 40 {
 41     if(col[rt]!=-1)
 42     {
 43         if(!hash[col[rt]]) cnt++;
 44         hash[col[rt]]=true;
 45         return;
 46     }
 47     if(l==r) return;
 48     int m=(l+r)>>1;
 49     
 50     query(lson);
 51     query(rson);
 52 }
 53 
 54 int Bin(int key,int n,int X[])
 55 {
 56     int l=0,r=n-1;
 57     while(l<=r)
 58     {
 59         int m=(l+r)>>1;
 60         
 61         if(X[m]==key) return m;
 62         if(X[m]<key) l=m+1;
 63         else r=m-1;
 64     }
 65     return -1;
 66 }
 67 
 68 int main()
 69 {
 70     int c,n;
 71     scanf("%d",&c);
 72     while(c--)
 73     {
 74         int nn=0;
 75         scanf("%d",&n);
 76         for(int i=0;i<n;i++)
 77         {
 78             scanf("%d%d",&li[i],&ri[i]);
 79             X[nn++]=li[i];
 80             X[nn++]=ri[i];
 81         }
 82         sort(X,X+nn);
 83         int m=1;
 84         
 85         for(int i=1;i<nn;i++)  //去掉重复的值，因为到时候(1)去位置的时候对于重复值去同样的的下标就可以。
 86         {
 87             if(X[i]!=X[i-1])
 88                 X[m++]=X[i];
 89         }
 90         
 91         for(int i=m-1;i>0;i--)  //通过向离散的不连续的线段点中添加随机数，使得线段不会出现覆盖不完全或者覆盖多
 92         {
 93             if(X[i]!=X[i-1]+1)
 94                 X[m++]=X[i-1]+1;
 95         }
 96         sort(X,X+m);
 97         memset(col,-1,sizeof(col));
 98         for(int i=0;i<n;i++)
 99         {//(1)
100             int l=Bin(li[i],m,X);   //按照贴海报的顺序依次向树中添加线段，
101             int r=Bin(ri[i],m,X);
102             update(l,r,i,0,m,1);
103         }
104         
105         memset(hash,false,sizeof(hash));
106         cnt=0;
107         query(0,m,1);
108         printf("%d
",cnt);  //记录露出来的海报数
109     }
110     return 0;
111 }

重写了

Hdu,4417

离散化，用pos记录它的位置，

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 
  6 #define lson l,m,rt<<1
  7 #define rson m+1,r,rt<<1|1
  8 
  9 using namespace std;
 10 
 11 const int maxn=100005;
 12 
 13 int ans[maxn];
 14 struct Node3
 15 {
 16     int l,r,cnt;
 17 }tree[maxn<<2];
 18 struct Node1
 19 {
 20     int l,r,h;
 21     int id;
 22     bool operator<(const Node1 x)const
 23     {
 24         return h<x.h;
 25     }
 26 }que[maxn];
 27 
 28 struct Node2
 29 {
 30     int val,pos;
 31     bool operator<(const Node2 x)const
 32     {
 33         return val<x.val;
 34     }
 35 }q[maxn];
 36 
 37 void build(int l,int r,int rt)
 38 {
 39     tree[rt].l=l;
 40     tree[rt].r=r;
 41     tree[rt].cnt=0;
 42     if(l==r) return;
 43     int m=(l+r)>>1;
 44     build(lson);
 45     build(rson);
 46 }
 47 
 48 void update(int rt,int x)
 49 {
 50     tree[rt].cnt++;
 51     if(tree[rt].l==tree[rt].r) return;
 52     
 53     int m=(tree[rt].l+tree[rt].r)>>1;
 54     if(x<=m) update(rt<<1,x);
 55     else if(x>m) update(rt<<1|1,x);
 56     
 57 }
 58 
 59 int query(int l,int r,int rt)
 60 {
 61     if(tree[rt].l==l && tree[rt].r==r)
 62     {
 63         return tree[rt].cnt;
 64     }
 65     
 66     int m=(tree[rt].l+tree[rt].r)>>1;
 67     
 68     if(r<=m) return query(l,r,rt<<1);
 69     else if(l>m) return query(l,r,rt<<1|1);
 70     else return query(l,m,rt<<1)+query(m+1,r,rt<<1|1);
 71 }
 72 
 73 int main()
 74 {
 75     int t,n,m;
 76     scanf("%d",&t);
 77     for(int i=1;i<=t;i++)
 78     {
 79         scanf("%d%d",&n,&m);
 80         for(int j=0;j<n;j++)
 81         {
 82             scanf("%d",&q[j].val);
 83             q[j].pos=j+1;
 84         }
 85         sort(q,q+n);
 86         
 87         for(int j=0;j<m;j++)
 88         {
 89             scanf("%d%d%d",&que[j].l,&que[j].r,&que[j].h);
 90             que[j].id=j;
 91         }
 92         
 93         sort(que,que+m);
 94         
 95         printf("Case %d:
",i);
 96         build(1,n,1);
 97         int k=0;
 98         for(int j=0;j<m;j++)
 99         {
100             while(k<n && q[k].val<=que[j].h)
101             {
102                 update(1,q[k].pos);
103                 k++;
104             }
105             ans[que[j].id]=query(que[j].l+1,que[j].r+1,1);
106         }
107         
108         for(int j=0;j<m;j++)
109             printf("%d
",ans[j]);
110     }
111     return 0;
112 }

View Code

活在现实，做在梦里。