众所周知 KDT 建树时维度选择有两种方法:轮换或者选方差最大的维度
今天给学弟讲课被叉了:点为 (0,0),(10,2),(20,0),(30,2),⋯(0,0),(10,2),(20,0),(30,2),\cdots(0,0),(10,2),(20,0),(30,2),⋯,方差优化会使每次都按 xxx 分割,询问矩形 (0,1)−(inf,3)(0,1)-(\inf,3)(0,1)−(inf,3),时间复杂度退化到 O(n)O(n)O(n)
求教是我的使用方式不对还是矩形查询不能方差优化