社区讨论

求助 KDT 方差优化

4401rk8
学术版参与者 7已保存回复 8

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@lo2asqeu
此快照首次捕获于
2023/10/23 10:48
2 年前
此快照最后确认于
2023/11/03 10:59
2 年前
查看原帖
众所周知 KDT 建树时维度选择有两种方法：轮换或者选方差最大的维度
今天给学弟讲课被叉了：点为 (0,0),(10,2),(20,0),(30,2),⋯(0,0),(10,2),(20,0),(30,2),\cdots，方差优化会使每次都按 xx 分割，询问矩形 (0,1)−(inf⁡,3)(0,1)-(\inf,3)，时间复杂度退化到 O(n)O(n)
求教是我的使用方式不对还是矩形查询不能方差优化

回复

共 8 条回复，欢迎继续交流。

正在加载回复...