数据结构-搜索树应用

给定一组区间，对于查询点，给出包含它的区间

• 区间树
• 线段树：还有更多应用……

二维（或高维）空间中，给定一组点，给出查询区域中包含的点

• 范围树
  • 时间复杂度：$O(r+{\log }^{d-1}n)$
  • 空间复杂度：$O(n{\log }^{d-1}n)$
• KD 树
  • 时间复杂度：$O(r+n^{1-1/d})$
  • 空间复杂度：$O(n)$