//只是自己做个备份

网络上好像没有几篇有介绍这个东西的

首先结构体

struct KDTree{
    int d[2],s[2],x[2],y[2];
}t[N];

d-维度，s-儿子，x-x坐标范围，y-y坐标范围

然后估价，这里的估价是算出下界或上界

距离最小：一个点离当前域的最短距离（内部为0）

距离最大：一个点离当前域端点的最长距离

以平面为例，(x,y)为查询的坐标

曼哈顿最小：

max(t[p].x[0]-x,0)+max(x-t[p].x[1],0)+max(t[p].y[0]-y,0)+max(y-t[p].y[1],0);

曼哈顿最大

max(abs(x-t[p].x[1]),abs(t[p].x[0]-x))+max(abs(y-t[p].y[1]),abs(t[p].y[0]-y));

欧几里德最小

sqr(max(max(x-t[p].x[1],t[p].x[0]-x),0))+sqr(max(max(y-t[p].y[1],t[p].y[0]-y),0))

欧几里德最大

max(sqr(x-t[p].x[0]),sqr(x-t[p].x[1]))+max(sqr(y-t[p].y[0]),sqr(y-t[p].y[1]))

切比雪夫距离？把坐标转45°就是曼哈顿距离了233