这个东西比较简单,复杂度又不会证(好像是假的),那就随便写一点吧

Brief Introduction

k-d tree是用来解决高维空间内一些操作的数据结构,OI中一般只用二维,下面都默认指二维

它大概长这样子:

19-3-24-1

简单来说,它是一棵二叉树的结构,每个节点代表了平面上的某一个部分

每次分叉的时候按照水平或竖直把当前部分分割成两半,直到平面内只剩一个点

构建

  • 确定当前平面内所有点极差最大的那一维
  • 按照这一维把所有点排序,找到中点,这一步可以用nth_element函数实现
  • 从中点把平面分割成两部分,递归处理

如果需要动态插入的话,还需要像替罪羊树一样动态拍扁重建

应用

最邻近查询

这一部分好像复杂度有问题,相当于是暴力加上了一些减枝

  • 模拟插入的过程,找到待查点在树上哪个节点所包含的部分,用经过的点与待查点的距离更新答案
  • 回溯的时候,如果当前点的另一个儿子有可能使答案更优,则访问另一个儿子

二维区间操作

我感觉这个复杂度应该是对的。。。

相当于把线段树扩展到二维,支持二维区间的一些操作。某些时候可以代替树套树/二维线段树,空间是O(n)O(n)的,更加优秀

这个很好理解,与线段树几乎一模一样

代码见此)