求助 KDT 方差优化
  • 板块学术版
  • 楼主401rk8
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/7/8 22:05
  • 上次更新2023/11/3 10:59:16
查看原帖
求助 KDT 方差优化
236866
401rk8楼主2023/7/8 22:05

众所周知 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)

求教是我的使用方式不对还是矩形查询不能方差优化

2023/7/8 22:05
加载中...