【编程之美】区间重合判断（线段树）
一，问题：
1. 给定一个源区间[x,y]和N个无序的目标区间[x1,y1] [x2,y2] ... [xn,yn]，判断源区间[x,y]是不是在目标区间内。
2. 给定一个窗口区域和系统界面上的N个窗口，判断这个窗口区域是否被已有的窗口覆盖。
二，解法：
问题一：
先用区间的左边界值对目标区间进行排序O(nlogn)，对排好序的区间进行合并O(n)，对每次待查找的源区间，用二分查出其左右两边界点分别处于合并后的哪个源区间中O(logn)，若属于同一个源区间则说明其在目标区间中，否则就说明不在。
#include <iostream>#include <algorithm>using namespace std;struct Line{int low, high;bool operator<(const Line &l) const{return low<l.low;}};#define MAXN 10001Line lines[MAXN];// 目标区间int ncnt = 0;// 合并后区间的个数#define N 101Line sl[N];// 待查询的源区间// 用二分查找找出key所在的区间，以区间的low作为划分int GetIndex(int key){int u, v;u = 0; v = ncnt-1;while (u<=v)// u,v可取等号{int m = (u+v)>>1;if (key >= lines[m].low)u = m+1;elsev = m-1;}return v;}int main(){int n, k, i, j;cin >> n >> k;// n是目标区间的个数,k是待查询的源区间的个数for (i=0; i<n; i++)cin >> lines[i].low >> lines[i].high;for (i=0; i<k; i++)cin >> sl[i].low >> sl[i].high;// 排序O(nlogn)sort(lines, lines+n);// 合并O(n)int lasthigh = lines[0].high;for (i=1; i<n; i++)if (lasthigh >= lines[i].low)lasthigh = lines[i].high;else{lines[ncnt++].high = lasthigh;lines[ncnt].low = lines[i].low;lasthigh = lines[i].high;}lines[ncnt++].high = lasthigh;for (i=0; i<k; i++){// 单词查找时间O(logn)int s1 = GetIndex(sl[i].low);int s2 = GetIndex(sl[i].high);if (s1==s2 && sl[i].high <= lines[s2].high)printf("Yes\n");elseprintf("No\n");}}
法二：使用并查集，对每个区间合并到一个子树上，最后判断源区间的x和y的根是否相同。
#include<iostream>using namespace std;const int size = 100;int father[size];int rank[size];void make_set(int n){ for(int i = 1; i <= n; i ++){ father[i] = i; rank[i] = 1; } }int find_set(int x)//寻找代表元素 { if(x != father[x]){ //元素不是单独的段，在某个区间内，返回某个区间代表 father[x] = find_set(father[x]); } return father[x];}void Union(int x, int y){ x = find_set(x); y = find_set(y); if(x == y){ //两个在同一个区间 return ; } if(rank[x] < rank[y]){ father[x] = y; } else{ father[y] = x; if(rank[x] == rank[y]){ rank[x] ++; } }}int main(){ int x1, y1; cin >> x1 >> y1;//输入要判断区间 int x, y; int n; cin >> n; //区间的个数 make_set(size); while(n --){ cin >> x >> y; //输入每个区间 if(x > y){//这一步很关键，表示考虑的周到 swap(x, y); } for(int i = x + 1; i <= y; i++){//将区间内的 段合并到已有区间 Union(x, i); } } if(find_set(x1) == find_set(y1)){ cout << "yes" << endl; } else{ cout << "no" << endl; } system("pause");}（1,3）结合后 father[1-3]=1 rank[1]=2;其余为1
（2,4）结合后 fahter[1-4]=1 rank[1]=2 ;其余为1
说明：（1，4）为整个区间，代表为1
法三：将无序的目标区间排序后，再合并成几个有序的区间，然后把源区间和有序的目标区间比较。
#include<iostream> #include<vector> using namespace std; typedef pair<int, int> section; bool cmp(section a, section b) { return a.first < b.first; } int main() { section src, tmp; cin >> src.first >> src.second; //要查找的 vector<section> v; while(cin >> tmp.first >> tmp.second, tmp.first | tmp.second){ v.push_back(tmp); } sort(v.begin(), v.end(), cmp);//按第一个域，从小到大排序 vector<section> res; vector<section>::iterator it = v.begin(); int begin = it->first;//记录区间的开始部分 int end = it->second;//记录区间的开始部分 if((it+1)==v.end()) //如果只有一个区间 res.push_back(make_pair(begin, end)); else { it ++; for(; it != v.end(); it++){ if(end <= it->first){ //如果第一个pair 的第二个元素，小于下一个pair 的第一个元素。 res.push_back(make_pair(begin, end)); //插入第一个区间 begin = it->first; end = it->second; } else if( (end > it->first) && (end <=it->second)) { //res.push_back(make_pair(begin, end); //插入第一个区间 //begin = it->first; end = it ->second; if((it+1)==v.end()) res.push_back(make_pair(begin, end)); } } } bool solve = false; it = res.begin(); for(; it != res.end(); it ++){ if(src.first >= it->first && src.second <= it->second){ solve = true; break; } } if(solve){ cout << "in" << endl; } else{ cout << "out" << endl; } system("pause"); }
问题二解法：
这个问题适合使用线段树来解答，单次查找的时间复杂度为O(nlogn)，当然也能用数组解答，但单次查找的时间复杂度会增加到O(n^2)。这里我们直接使用线段树来解答。
线段树是一棵二叉树，将数轴划分成一系列的初等区间[I, I+1] (I=1,2,..,N-1)。每个初等区间对应于线段树的一个叶结点。线段树的内部结点对应于形如[ I, J ](J – I > 1)的一般区间。由于线段树给每一个区间都分配了结点，利用线段树可以求区间并后的总长度与区间并后的线段数。先给出测试数据（前4行是系统界面上已有的N个窗口，之后的一行是待测试的窗口区域），后面是代码：
4
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
#include <iostream>#include <cmath>#include <algorithm>using namespace std;// 线段树的结点struct SegNode{ int low, high;// 线段的两端点索引 int ncover;// 线段被覆盖的次数 SegNode *left;// 结点的左子树 SegNode *right;// 结点的右子树 SegNode() {low=high=0;ncover=0;left=right=NULL;}};// 构造线段树，它是一个完全二叉树void BuildSegTree(SegNode *&tree, int *index, int low, int high){ if (low < high) { tree = new SegNode; tree->low = low; tree->high = high; if (high-low>1) { int m = (low+high)/2; BuildSegTree(tree->left, index, low, m); BuildSegTree(tree->right, index, m, high); } }}// 往线段树中插入线段，即用线段(low,high)来覆盖线段树void InsertSegTree(SegNode *tree, int low, int high){ // 先序遍历 if (low<=tree->low && tree->high<=high) tree->ncover++; else if (tree->high-tree->low > 1) { int m = (tree->low+tree->high)/2; if (low < m) InsertSegTree(tree->left, low, high); if (m < high) InsertSegTree(tree->right, low, high); }}// 从线段树中删除线段void DeleteSegTree(SegNode *tree, int low, int high){ if (low<=tree->low && tree->high<=high) tree->ncover--; else if (tree->high-tree->low > 1) { int m = (tree->low+tree->high)/2; if (low < m) DeleteSegTree(tree->left, low, high); if (m < high) DeleteSegTree(tree->right, low, high); }}// 线段树中是否包含线段(low,high)bool FindSegTree(SegNode *tree, int low, int high){// 若当前区间被覆盖，且线段(low,high)属于当前区间则返回覆盖if (tree->ncover && tree->low <= low && high <= tree->high )return true;// 若(low,high)没被当前区间覆盖，则将其分为两段，// 分别考虑是否被子结点表示的区间覆盖else if (tree->high - tree->low > 1){int m = (tree->low + tree->high) >> 1;bool ret = true;if (low<m) ret = FindSegTree(tree->left, low, high<m?high:m);if (!ret) return false;if (m<high) ret = FindSegTree(tree->right, m<low?low:m, high);if (!ret) return false;return true;}return false;}#define LEFT true#define RIGHT false#define INF 10000// 表示竖直方向的线段struct Line{ int starty, endy;// 竖线的长度 int x;// 竖线的位置 bool inout;// 竖线是长方形的左边还是右边 bool operator<(const Line& a) const{// 依据x坐标进行排序 return x<a.x; }};// 所有竖直方向的线段Line lines[INF];// 对横向超元线段进行分组int index[INF];int nCnt = 0;// 获取key的位置int GetIndex(int key){// 用二分查找查出key在index中的位置return lower_bound(index,index+nCnt,key)-index;}// 获取key的位置或比它小的最大数的位置int GetLower(int key){size_t pos = lower_bound(index,index+nCnt,key)-index;if (key == index[pos]) return pos;else return pos-1;}// 获取key的位置或比它大的最小数的位置int GetUpper(int key){return lower_bound(index,index+nCnt,key)-index;}int main(){ int nRec; cin >> nRec; int i, j; int x[2], y[2]; // 读取nRec个窗口的数据 for (i=0; i<nRec; i++) { cin >> x[0] >> y[0] >> x[1] >> y[1];// 记录每个长方形的两条竖直边 lines[2*i].x=x[0];lines[2*i+1].x=x[1]; lines[2*i].starty=lines[2*i+1].starty=min(y[0],y[1]); lines[2*i].endy=lines[2*i+1].endy=max(y[0],y[1]); lines[2*i].inout=LEFT;lines[2*i+1].inout=RIGHT;// 对竖直的线段进行离散化 index[2*i]=y[0];index[2*i+1]=y[1]; } // 待查询的窗口区域 Line search[2]; cin >> x[0] >> y[0] >> x[1] >> y[1]; search[0].x=x[0];search[1].x=x[1]; search[0].starty=search[1].starty=min(y[0],y[1]); search[0].endy=search[1].endy=max(y[0],y[1]); search[0].inout=LEFT;search[1].inout=RIGHT; // 对x坐标进行排序O(nlogn) sort(index, index+2*nRec); sort(lines, lines+2*nRec); // 排除index数组中的重复数据O(n) for (i=1; i<2*nRec; i++) if (index[i]!=index[i-1]) index[nCnt++] = index[i-1]; index[nCnt++] = index[2*nRec-1]; // 建立线段树 SegNode *tree; BuildSegTree(tree, index, 0, nCnt-1); // 单词查找的时间复杂度为O(nlogn) bool res; InsertSegTree(tree, GetIndex(lines[0].starty), GetIndex(lines[0].endy)); for (i=1; i<2*nRec; i++) { if (lines[i].inout==LEFT)// 遇窗口的左边界，将其加入线段树 InsertSegTree(tree, GetIndex(lines[i].starty), GetIndex(lines[i].endy)); else// 遇窗口的右边界，将其删出线段树 DeleteSegTree(tree, GetIndex(lines[i].starty), GetIndex(lines[i].endy));if (lines[i].x!=lines[i-1].x && search[0].x < lines[i+1].x && search[1].x > lines[i].x){// 从待查窗口区域的左边界开始查询直到其右边界结束查询res = FindSegTree(tree, GetLower(search[0].starty), GetUpper(search[0].endy));if (!res) break;}else if (search[1].x <= lines[i].x)break; } if (res) printf("Yes\n"); elseprintf("No\n"); return 0;}