K-D Tree 基础练习
题单介绍
求收藏 QwQ...
如果发现本题单有任何不妥或有未收录的 KDT 好题，可以私信。
动态更新
## $\text{K-D Tree}$
```K-D Tree``` 是一种维护多维点信息的数据结构，这些点一般在二维及以上。时空效率可观并且有很多用处。所以掌握这个数据结构还是有必要的。
虽说 CDQ 分治 跑地比这个快，但思维难度也比 KDT 大一些，更何况要是 ***强制在线*** 的话，情况就完全反转的。
大部分 KDT 的变式都需要剪枝。
- *下面的难度都是自己按做题感受分的，没必要卡得太死*
### $\texttt{Level I}$
大概是板子题左右的难度，放心切。
- P4148 简单题（二维数点）
- P4390 [BOI2007]Mokia 摩基亚（二维数点）
- P3810【模板】三维偏序（陌上花开）（三维数点）
- *P4169 [Violet]天使玩偶/SJY摆棋子（二维最近距离，注意这里 KDT 的时间复杂度是不对的，一般仅供加强掌握）
- P2479 [SDOI2010]捉迷藏（和 P4196 做法相似）
- P6224 [BJWC2014]数据（和 P4196 做法相似）
### $\texttt{Level II}$
稍微加一点技巧，但稍微想一想就通了。
- P3769 [CH弱省胡策R2]TATT（KDT 优化dp）[推一下本蒟蒻的题解](https://strncmp.blog.luogu.org/solution-p3769)
- P5621 [DBOI2019]德丽莎世界第一可爱（和 P3769 做法相似）[再推一下](https://strncmp.blog.luogu.org/solution-p5621)
- P4357 [CQOI2016]K远点对（堆在 KDT 上的应用）
- P4475 巧克力王国（改变一下边界）
- P4793 [AHOI2008]矩形藏宝地（转个弯）
- P2093 [国家集训队]JZPFAR（和 P4357 做法相似）
### $\texttt{Level III}$
接下来就没有这么简单了。。
- P4509 [CTSC2015]葱（可持久化）
- P5471 [NOI2019]弹跳（KDT 优化建图，好像有点卡常的亚子）
- P4631 [APIO2018] Circle selection 选圆圈（一个结点维护一个矩形）
- P4848 崂山白花蛇草水（权值线段树套 KDT）
> 如果您刷完了以上的题，那说明您的水平已经可以了！