线段树札记
线段树不是区间树，线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。注意他是把一段连续的区间分为单元区间为叶子节点的一颗数，以此为基础，展开一系列牛逼的计算。
首先就是如何建立这么一个线段树？
如此递归地建立，对于线段树中的每一个非叶子节点[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)/2construct(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)/2if mid >=end insert(2*index,begin,end)else insert(2*index+1,begin,end)endend |
这里为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].coverelse return
query(2*index+1,x)+tree[index].coverend |
题目练习
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 50010struct
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
原文：http://www.cnblogs.com/championlai/p/3721829.html