首页 > 代码库 > 线段树入门---给定多个线段求点的出现个数

线段树入门---给定多个线段求点的出现个数

线段树是一颗二叉树,他的每个节点都是一个区间,此题为线段树的入门题目,只是学习笔记。例题:给定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

结果如图:

线段树入门---给定多个线段求点的出现个数