首页 > 代码库 > 线段树入门---给定多个线段求点的出现个数
线段树入门---给定多个线段求点的出现个数
线段树是一颗二叉树，他的每个节点都是一个区间，此题为线段树的入门题目，只是学习笔记。例题：给定N个线段，给定M个点，求点在多少个线段中出现过，此时如果用传统的方法来求，时间复杂度太高，但是，线段树的时间复杂度还可以接受。
步骤为：
1. 首先找一个区间，能覆盖给定的所有区间， 然后把此区间建立线段树，建立线段树的方式是二分法建立，即它的左孩子是他的左半个区间，右孩子是它的右边那个区间。一个图足以说明清楚
2. 将所有的区间映射到此树上， 从根节点开始遍历， 每遍历一个节点考虑四种情况：
1） 当前节点的区间正好和正在遍历的区间相等，这时， 将它的cnt++， 然后return
2） 当区间在当前节点的左半个区间时，继续遍历当前节点的左孩子
3） 当区间在当前节点的右半个区间时，继续遍历当前节点的右孩子
4） 除了上面的之外， 区间的左端点在区间中点的左边，右端点在区间中点的右边，这时分别遍历左右孩子
3. 此时的树已经是映射好的，所以只需要查找点就行了，也是用递归的形式，只要加它的cnt就行了
下面是代码实现：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 5 using namespace std; 6 7 const int MAX = 999999999; 8 const int MIN = 0; 9 //left，right表示区间的左右端点，cnt表示这样的线段有多少条 10 typedef struct Node{ 11 int left, right; 12 int cnt; 13 struct Node *lchild, *rchild; 14 }Node, *PNode; 15 //创建线段树函数 16 void CreateTree(PNode *root)//*root已经被初始化 17 { 18 int left = (*root)->left; 19 int right = (*root)->right; 20 if(left < right) 21 { 22 int mid = (left + right) / 2; 23 //它的左孩子,并初始化它的左孩子 24 PNode lnode = (PNode)malloc(sizeof(Node)); 25 lnode->cnt = 0; 26 lnode->left = left; 27 lnode->right = mid; 28 lnode->lchild = lnode->rchild = NULL; 29 //它的右孩子,并初始化它的右孩子 30 PNode rnode = (PNode)malloc(sizeof(Node)); 31 rnode->cnt = 0; 32 rnode->left = mid + 1; 33 rnode->right = right; 34 rnode->rchild = rnode->lchild = NULL; 35 //扯上关系 36 (*root)->lchild = lnode; 37 (*root)->rchild = rnode; 38 //递归建树 39 CreateTree(&(*root)->lchild); 40 CreateTree(&(*root)->rchild); 41 } 42 } 43 //将区间映射到线段树上 44 void Map_Interval(PNode root, int left, int right) 45 { 46 //如果恰好当前区间等于线段树当前节点的区间，将该条线段+1，就返回 47 if(root->left == left && root->right == right) 48 { 49 root->cnt++; 50 return; 51 } 52 int mid = (root->left + root->right) / 2; 53 //如果在当前节点的区间左半个区间内， 就继续找他的左半个区间，也就是左儿子 54 if(right <= mid) 55 { 56 Map_Interval(root->lchild, left, right); 57 } 58 //如果在当前节点的区间右半个区间内， 就继续找他的右半个区间，也就是右儿子 59 else if(left > mid) 60 { 61 Map_Interval(root->rchild, left, right); 62 } 63 //如果左端点在当前节点的左半部份，右端点在当前区间的右半部份，分别找 64 else 65 { 66 Map_Interval(root->lchild, left, mid); 67 Map_Interval(root->rchild, mid + 1, right); 68 } 69 } 70 //找到这个点在线段上一共出现的次数， sum用来得到具体的数目， point为点的号 71 void search_point(PNode root, int point, int *sum) 72 { 73 if(point == root->left && point == root->right) 74 { 75 *sum += root->cnt; 76 return; 77 } 78 else 79 { 80 int mid = (root->left + root->right) / 2; 81 if(point > mid) 82 { 83 *sum += root->cnt; 84 search_point(root->rchild, point, sum); 85 } 86 else 87 { 88 *sum += root->cnt; 89 search_point(root->lchild, point, sum); 90 } 91 } 92 } 93 //前序遍历，辅助看建树的情况 94 void preOrder(PNode root) 95 { 96 if(root != NULL) 97 { 98 printf("[%d, %d] count --> %d\n", root->left, root->right, root->cnt); 99 preOrder(root->lchild);100 preOrder(root->rchild);101 }102 }103 104 int main()105 {106 freopen("1.in", "r", stdin);107 //初始化root108 PNode root = (PNode)malloc(sizeof(Node));109 root->cnt = 0;110 root->lchild = root->rchild = NULL;111 112 int left[1000], right[1000], point[1000];113 int n; //区间个数114 scanf("%d", &n);115 int min_num = MAX;//保存最小的区间端点116 int max_num = MIN;//保存最大的区间端点117 for(int i = 0; i < n; i++)118 {119 scanf("%d %d", &left[i], &right[i]);120 min_num = min(left[i], min_num);121 max_num = max(right[i], max_num);122 }123 int m;//带查询点的个数124 scanf("%d", &m);125 for(int i = 0; i < m; i++)126 scanf("%d", &point[i]);127 root->left = min_num;128 root->right = max_num;129 CreateTree(&root);//建树130 preOrder(root);//打印出来，看建树的情况131 for(int i = 0; i < n; i++)132 {133 Map_Interval(root, left[i], right[i]);134 }135 //将区间映射到树上之后，再看树的情况136 printf("\n=================================================\n");137 preOrder(root);138 int tmp = 0;139 for(int i = 0; i < m; i++)140 {141 search_point(root, point[i], &tmp);142 printf("%d 在给定线段中出现 %d 次\n", point[i], tmp);143 tmp = 0;144 }145 return 0;146 }
其中利用文件重定向打开文件，文件中的内容为
3
2 5
4 6
0 7
4
2 4 6 7
结果如图：
线段树入门---给定多个线段求点的出现个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。