首页 > 代码库 > 线段树
线段树
线段树札记
线段树不是区间树,线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。注意他是把一段连续的区间分为单元区间为叶子节点的一颗数,以此为基础,展开一系列牛逼的计算。
首先就是如何建立这么一个线段树?
如此递归地建立,对于线段树中的每一个非叶子节点[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