首页 > 代码库 > 线段树

线段树

2024-07-04 01:45:52   234人阅读

线段树札记

 

线段树不是区间树，线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。注意他是把一段连续的区间分为单元区间为叶子节点的一颗数，以此为基础，展开一系列牛逼的计算。

首先就是如何建立这么一个线段树？

如此递归地建立，对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。就可以建立一张如下图的线段树：

 

  伪代码：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  construct(index,left,right) {
 
 tree[index].left = left;
 
 tree[index].right = right;
 
 if left=right
 
   return;
 
 mid = (left+right)/2
 
construct(2*index,left,mid)
 
construct(2*index+1,mid+1,right)
 
}

　　 如此一个线段树就创建好了，父亲节点与孩子节点是index->(2*index,2*index+1),用此来创建一颗二叉树，所以在结构体里面只需要两个字段一个是left，一个是right

  创建好线段树之后，一个重要操作就是插入操作，这个是奠定后面各种牛逼操作的基础。那么如何插入一段区间呢？(假设区间为[begin,end])

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
insert(index,begin,end)
 
if begin=tree[index].left&&end=tree[index].right=end  //注意这里是等于号
 
  tree[index].cover++
 
int mid = (tree[index].left+tree[index].right)/2
 
if mid >=end
 
  insert(2*index,begin,end)
 
else
 
  insert(2*index+1,begin,end)
 
end
 
end

这里为cover添加了一个字段cover，计算这段区间的区间

这个cover是后面用来查询用的

 

到目前为止，该用的数据结构已经维护好了。现在开始用了，查询一个点在区间中出现的次数。 从根节点开始到[x,x]叶子的这条路径中所有点计数相加方为x出现次数 

 查询x在区间中出现的次数。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
query(index,x)
 
 mid = (tree[index].left + tree[index].right)/2
 
 if x<=mid
 
  return query(2*index,x)+tree[index].cover
 
else
 
  return query(2*index+1,x)+tree[index].cover
 
end

题目练习　

1,单点更新

 HDU 敌兵布阵

 题目很简单就是一道赤裸裸的线段树的题目。不过好久没敲代码了，生疏了，还是被一些小问题搞得很烦，可能自己内心也是太烦了。

 最坑爹的是strcmp(str,"End")和str=="End"字符串的比较吧

 占位符。。。。。。。。。。。。。

 对于一个单节点更新的时候可以从上往下寻找的时候就更新节点的cover域，也可以在回朔的时候更新节点的cover域；

 

?
1
2
3
4
5
6
if(x>=tree[index].left&&x<=tree[index].right) // >=  -> ==
 {
     tree[index].cover += value;
     if(tree[index].left==x&&tree[index].right==x)
         return;
 }

 也可以在

?
1
2
3
4
5
6
int mid=(tree[index].left+tree[index].right)/2;
   if(mid>=x) //sometime i forget to consider the equal condition,but it‘s important;
      update(2*index,x,value);
   else
      update(2*index+1,x,value);
   //tree[index].cover += value; 对于单节点更新，是在查找的时候更新父亲节点，还是回朔时候更新父亲节点都是可行的

代码：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<stdio.h>
#include<string.h>
 
#define MAX 50010
 
struct Node
{
       int left;
       int right;
       int cover;
};
Node * tree= new Node[MAX*4];
 
int data[MAX];
 
void build(int index,int left,int right)
{
     tree[index].left = left;
     tree[index].right= right;
     //printf("%d %d %d\n",index,left,right);
     if(left==right)
     {
        tree[index].cover = data[left];
        // printf("%d %d %d %d\n",index,left,right,tree[index].cover);
        return;
     }
     int mid = (left+right)/2;
     build(2*index,left,mid);
     build(2*index+1,mid+1,right);
     tree[index].cover = tree[2*index].cover + tree[2*index+1].cover; //update parent‘s cover field,not just update leaf node  
}
 
void update(int index,int x,int value)
{
      
     //printf("%d %d %d\n",index,tree[index].left,tree[index].right);
     if(x>=tree[index].left&&x<=tree[index].right) // >=  -> ==
     {
         tree[index].cover += value;
         if(tree[index].left==x&&tree[index].right==x)
             return;
     }
 
     int mid=(tree[index].left+tree[index].right)/2;
     if(mid>=x) //sometime i forget to consider the equal condition,but it‘s important;
        update(2*index,x,value);
     else
        update(2*index+1,x,value);
     //tree[index].cover += value; 对于单节点更新，是在查找的时候更新父亲节点，还是回朔时候更新父亲节点都是可行的
}
 
int query(int index,int left,int right)
{
    //printf("%d %d %d\n",index,left,right);
    //getchar();
    if(left==tree[index].left&&right==tree[index].right)
    {
       return tree[index].cover;
    }
    int mid=(tree[index].left+tree[index].right)/2;
    if(mid>=right)
       return query(2*index,left,right);
    else if(mid<left)
       return query(2*index+1,left,right);
    else
       return query(2*index,left,mid)+query(2*index+1,mid+1,right);
}
 
int main()
{
    int T,N;
    char  str[20];
    scanf("%d",&T);
    int p,v;
    for(int s = 1; s <= T;s++)
    {
       //printf("%d",MAX*4);
       memset(tree,0,sizeof(Node)*MAX*4);
       memset(data,0,sizeof(int)*MAX);
       scanf("%d",&N);
       for(int i = 1; i<=N;i++)
       {
        scanf("%d",&data[i]);
       }
       build(1,1,N);
     //  for(int i = 1;i<=4*N;i++)
    //   {
    //      printf("%d ",tree[i].cover);
   //    }
       printf("Case %d:\n",s);
       while(true) //while(scanf("%s",str)&&str!="End") str为End时候不起作用
       {
           scanf("%s",str);
          // printf("%s",str);
           if(strcmp(str,"End")==0)
              break;
           scanf("%d%d",&p,&v);
           if(strcmp(str,"Add")==0)
           {
             update(1,p,v);                      
           }else if(strcmp(str,"Sub")==0){
             update(1,p,-v);
           }
           else if(strcmp(str,"Query")==0)
           {
             printf("%d\n",query(1,p,v));
           }
       } 
      // printf("end %d",s);
    }
    return 0;
}

 

推荐文章：

    http://blog.csdn.net/wypblog/article/details/8219727

 

 


联系
我们