大概就是个复杂度对的暴力做法，在你不想写二维线段树等的时候优秀的替代品。
优点：思路简单，代码好写。
他大概有两种用法（虽然差不多）。
在平面坐标系中干一些事情：
例如最常规的平面最近最远点，不管是欧几里得距离还是曼哈顿距离，本质上都是一样的。
利用不同维度的尽量平均的分割，再在询问时剪枝。
这里给出一个曼哈顿距离上的最近最远距离的版本，可供参考：
namespace KD {
int Rt, lc[N], rc[N], u[N], d[N], l[N], r[N];
inline void Merge(int x, int y) {
u[x] = std::max(u[x], u[y]);
d[x] = std::min(d[x], d[y]);
l[x] = std::min(l[x], l[y]);
r[x] = std::max(r[x], r[y]);
}
inline void Up(int t) {
l[t] = r[t] = p[t].v[];
u[t] = d[t] = p[t].v[];
if (lc[t]) Merge(t, lc[t]);
if (rc[t]) Merge(t, rc[t]);
}
int Build(int l, int r, int dep) {
if (l >= r) {
if (l == r) Up(l);
return (l == r)? (l) : ();
}
Mt = dep & ; int md = (l + r) >> ;
std::nth_element(p + l, p + md, p + + r);
lc[md] = Build(l, md - , dep + );
rc[md] = Build(md + , r, dep + );
Up(md); return md;
}
inline int In_mi(int t) {
int re = ;
re += std::max(qi.v[] - r[t], );
re += std::max(l[t] - qi.v[], );
re += std::max(qi.v[] - u[t], );
re += std::max(d[t] - qi.v[], );
return re;
}
inline int In_ma(int t) {
int re = ;
re += std::max(std::abs(qi.v[] - r[t]), std::abs(qi.v[] - l[t]));
re += std::max(std::abs(qi.v[] - u[t]), std::abs(qi.v[] - d[t]));
return re;
}
void Query_mi(int t, int dep) {
if (!t) return; Mt = dep & ;
if (qi != p[t]) ani = std::min(ani, Dis(qi, p[t]));
int dl = (lc[t])? (In_mi(lc[t])) : (INF);
int dr = (rc[t])? (In_mi(rc[t])) : (INF);
if (dl < dr) {
if (ani > dl) Query_mi(lc[t], dep + );
if (ani > dr) Query_mi(rc[t], dep + );
} else {
if (ani > dr) Query_mi(rc[t], dep + );
if (ani > dl) Query_mi(lc[t], dep + );
}
}
void Query_ma(int t, int dep) {
if (!t) return; Mt = dep & ;
ana = std::max(ana, Dis(qi, p[t]));
int dl = (lc[t])? (In_ma(lc[t])) : ();
int dr = (rc[t])? (In_ma(rc[t])) : ();
if (dl > dr) {
if (ana < dl) Query_ma(lc[t], dep + );
if (ana < dr) Query_ma(rc[t], dep + );
} else {
if (ana < dr) Query_ma(rc[t], dep + );
if (ana < dl) Query_ma(lc[t], dep + );
}
}
}
通常带有表示点的结构体：
struct No {
int v[];
inline void Read() {
scanf("%d%d", &v[], &v[]);
}
inline friend bool operator < (No a, No b) {
return a.v[Mt] < b.v[Mt];
}
} p[N], qi;
（注：$qi$表示当前询问点，$Mt$表示当前分割的维度）
当然还有某些问题要求第$k$远点，只要每次查到一个点就扔到堆里去，时时维护最远的$k$个就好了，因为KD-tree剪掉了很多不必要的点，所以可以认为扔到堆里的元素并不多。
或者说动态的问题需要动态开点，开多了就可能导致树不平衡，隔一会重构就好了。
当然KD-tree在坐标系上最大的优越之处在于乱搞，旋转一下坐标系之后什么都拦不住KD-tree啦。
比如说APIO 2018的选圈圈。。。把圆用矩形框起来，每次暴力找就好了。
#include <cstdio>
#include <algorithm> const int N = ;
const double Alpha = 1.926, EPS = 1e-; int n, Mt, ans[N]; struct No {
double v[], r; int id;
inline void Read(double x = , double y = ) {
scanf("%lf%lf%lf", &x, &y, &r);
v[] = x * cos(Alpha) + y * sin(Alpha);
v[] = y * cos(Alpha) - x * sin(Alpha);
}
inline friend bool operator < (No a, No b) {
return a.v[Mt] < b.v[Mt];
}
} pp[N], p[N], qi; inline bool cmp_r(No a, No b) {
return (a.r == b.r)? (a.id < b.id) : (a.r > b.r);
}
inline double Sqr(double x) {
return x * x;
} namespace KD {
int Rt, lc[N], rc[N];
double l[N], r[N], d[N], u[N];
inline void Merge(int x, int y) {
l[x] = std::min(l[x], l[y]);
r[x] = std::max(r[x], r[y]);
d[x] = std::min(d[x], d[y]);
u[x] = std::max(u[x], u[y]);
}
inline void Up(int t) {
l[t] = p[t].v[] - p[t].r;
r[t] = p[t].v[] + p[t].r;
d[t] = p[t].v[] - p[t].r;
u[t] = p[t].v[] + p[t].r;
if (lc[t]) Merge(t, lc[t]);
if (rc[t]) Merge(t, rc[t]);
}
int Build(int l, int r, int dep) {
if (l >= r) return (l == r)? (Up(l), l) : ();
Mt = dep & ; int md = (l + r) >> ;
std::nth_element(p + l, p + md, p + + r);
lc[md] = Build(l, md - , dep + );
rc[md] = Build(md + , r, dep + );
Up(md); return md;
}
inline int Out(int t) {
int re1 = r[t] < qi.v[] - qi.r - EPS || l[t] > qi.v[] + qi.r + EPS;
int re2 = u[t] < qi.v[] - qi.r - EPS || d[t] > qi.v[] + qi.r + EPS;
return re1 || re2;
}
inline int Check(int t) {
return Sqr(p[t].r + qi.r) + EPS >= Sqr(p[t].v[] - qi.v[]) + Sqr(p[t].v[] - qi.v[]);
}
void Query(int t) {
if (!t || Out(t)) return;
if (!ans[p[t].id] && Check(t)) ans[p[t].id] = qi.id;
if (lc[t]) Query(lc[t]);
if (rc[t]) Query(rc[t]);
}
} int main() {
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
p[i].Read();
p[i].id = i;
pp[i] = p[i];
}
std::sort(pp + , pp + + n, cmp_r);
KD::Rt = KD::Build(, n, ); for (int i = ; i <= n; ++i) {
if (!ans[pp[i].id]) {
ans[pp[i].id] = pp[i].id;
qi = pp[i];
KD::Query(KD::Rt);
}
}
for (int i = ; i <= n; ++i) {
printf("%d ", ans[i]);
} return ;
}
二维线段树的替代品：
由于KD-tree本身就和值域没有什么关系，涉及到二维数点、矩形修改、矩形询问等问题可以比较方便的做，只要每个点维护一个矩形，然后大致就和线段树差不多了。
其实很多问题都能转化为二维平面甚至多维上的数点问题，有些问题离线后把时间也算成一维也是一个常用套路，KD-tree在这方面处理能力较强，适用范围较广。
要注意KD-tree上每一个点都是一个真实的点，修改时不要忘记更新它本身。
可能左右两个子节点表示的矩形存在相交，有时候自顶向下不一定好。