首页 > 代码库 > 每周一题——坐标点范围查询
每周一题——坐标点范围查询
在平面坐标系中有若干点P={p[1],p[2],…,p[n]}，点p[i]的坐标为(p[i].x，p[i].y)，给定一个位置范围R=（west, east, south, north）,
求P中所有符合条件west < p[i].x < east，south < p[i].y < north的点p[i]构成的集合PR的过程，称为范围查询。
请设计一个利于查询的数据结构，及相应的构造和查询算法，使范围查询能够快速执行。
注：构造是指将输入数据P从数组格式转换为你所设计的数据结构格式的过程。查询的算法复杂度要尽量低，构造过程的算法复杂度可以略高。
N可能非常大，不可以使用遍历所有N个点的方式进行查询。
求P中所有符合条件west < p[i].x < east，south < p[i].y < north的点p[i]构成的集合PR的过程，称为范围查询。
请设计一个利于查询的数据结构，及相应的构造和查询算法，使范围查询能够快速执行。
注：构造是指将输入数据P从数组格式转换为你所设计的数据结构格式的过程。查询的算法复杂度要尽量低，构造过程的算法复杂度可以略高。
N可能非常大，不可以使用遍历所有N个点的方式进行查询。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。