\(K-D Tree\),一种用来维护\(K\)维数据的数据结构。常用于维护各种高维的数据，或者是邻近搜索等。从另一种意义上说，实际上就是高维的二叉搜索树。对于一些常见的问题，如\(k\)远点对、三位偏序（在线）等，可以用\(K-DTree\)解决。

那么，\(KDT\)如何建树呢？

观察一下普通的二叉搜索树，发现它的每一个节点都有一个“关键字",用它来划分左右儿子。于是，对于高维的数据，我们考虑分层划分。

比如对于点\((x,y)\)，它有两层维度。那么，我们可以在第一层用\(x\)划分，第二层用\(y\)划分，第三层用\(x\)划分，依次迭代。也可以用随机数的方法，随机划分。

对于第\(i\)层维度，我们对它的维度编号是\(i-1\).

接下来考虑如何实现建树。

首先，这个树上得维护一些东西，要不然就没啥意义了。对于一个节点，我们首先要知道它所管辖的区域有哪些。那么对于\(k\)维的数据，我们定义树中维护两个数组：

\(int\) \(mi[k],mx[k]\)来维护每一层它所能维护到的上界和下界。

其次，我们可以用\(siz\)来维护它的子树大小（用于重构），以及题目中要求的信息。

对于区间\([l,r]\)，我们依旧是按照套路，将它划分为左右两个区间，并分别递归。

注意选择每个点中管辖的区域中哪个点做根的时候，比较优的是中位数。于是，我们建树的时候，就优先使用中位数来做这个孩子的点，就是所谓这颗子树的\(rt\)点。

那么，怎么找中位数呢？\(k\)维，每一层都做一次\(sort\)，那不得炸上天？

这样的复杂度是\(O(knlogn)\)的（一本正经地瞎蒙）

所以我们考虑换一个方式。\(STL\)自然会给我们另一条路的：\(nth\)_\(element\)函数就可以满足我们的需求。

它可以做到对于一个\([l,r]\)的序列，用\(O(n)\)的时间，使得我们所选择的的那个位置\(pos\)上处于合适的数字。但是注意，除了这个位置上，其它位置上没有被排序。

但是我们只需要这么多就够了，不是吗？

用它的时候，别忘了重载一下运算符。

于是，\(build\)建树的代码就呼之欲出了……

int build(int l,int r,int d){

	if(l>r)return 0;

	int x=++tot,mid=l+r>>1;

	D=d;nth_element(p+l,p+mid,p+r+1);

	tr[x].c=p[mid];ls[x]=build(l,mid-1,d^1);

	rs[x]=build(mid+1,r,d^1);pushup(x);return x;

}

还记得当初学那些什么乱七八糟的平衡树的时候，总会有不平衡的情况。同样地，\(KDT\)也可以支持动态插入，而不平衡也是我们要解决的问题之一。

相信各位听过一句话：优美的暴力（逃）

记得有个东西叫替罪羊树吗，里面有个东东叫重构。我们引入它的概念，来实现\(KDT\)的平衡。

设定平衡因子\(Alpha\)，来检测是否不平衡，不平衡则重建。记住，数据维度要对应上。

对于空间，开一个垃圾桶（雾），保存删掉的节点的编号，循环利用一下。

下面给出这部分代码：

inline int New(){

	if(top)return rub[top--];

	else return ++tot;

}

inline int build(int l,int r,int d){

	if(l>r)return 0;

	int x=New(),mid=l+r>>1;

	D=d;nth_element(p+l,p+mid,p+r+1);

	tr[x].c=p[mid];ls[x]=build(l,mid-1,d^1);

	rs[x]=build(mid+1,r,d^1);pushup(x);return x;

}

inline void clear(int x,int pos){

	if(ls[x])clear(ls[x],pos);

	p[pos+tr[ls[x]].siz+1]=tr[x].c;rub[++top]=x;

	if(rs[x])clear(rs[x],pos+tr[ls[x]].siz+1);

}

inline void check(int &x,int d){

	double C=A*(double)(tr[x].siz);

	if(C<(double)(tr[ls[x]].siz)||C<(double)(tr[rs[x]].siz)){

		clear(x,0);

		x=build(1,tr[x].siz,d);

	}

}

inline void Ins(int &x,point p,int d){

	if(!x){x=New();ls[x]=rs[x]=0;tr[x].c=p;pushup(x);return;}

	if(p.x[d]<=tr[x].c.x[d])Ins(ls[x],p,d^1);

	else Ins(rs[x],p,d^1);

	pushup(x);check(x,d);

}

里面的\(A\)就是阿尔法。

好了，现在看看它都（干了些什么）能干什么吧。

例题：\(K\)远点对#

求出\(n\)个点中，对于指定点，第\(k\)大的欧氏距离的平方。

这玩意，用一个堆和\(KDT\)结合就好了。

对于第\(k\)大，堆里面\(push\)进\(2k\)个0.因为，对于每个点，我找到的都是不定向的，所以同一个点会两次被搜到。于是，堆要到\(2k\).

对于每一次搜到的答案，和堆顶比较，如果大就放进去，并去掉堆尾，并以每一次的答案去搜索左右子树（没错，它是靠剪枝吃饭哒）

对于一个点到管辖范围的查询……意会即可（雾

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<string>

using namespace std;

#define inf 192608170000000ll

typedef long long ll;

ll read(){

    ll x=0,pos=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;

    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';

    return pos?x:-x;

}

const ll MAXN=2e5+10;

ll n,k;

struct point{

	ll x[2];

}p[MAXN];

struct cmp{

	ll operator()(ll a,ll b){

		return a>b;

	}

};

priority_queue<ll,vector<ll>,cmp>q;

struct node{

	ll minn[2],maxn[2],siz;

	point c;

}tr[MAXN];

ll rt,D,rs[MAXN],ls[MAXN];

ll operator<(point a,point b){return a.x[D]<b.x[D];}

inline void pushup(ll x){

	ll l=ls[x],r=rs[x];

	tr[x].siz=tr[l].siz+tr[r].siz+1;

	for(register int i=0;i<=1;++i){

		tr[x].minn[i]=tr[x].maxn[i]=tr[x].c.x[i];

		if(l)tr[x].minn[i]=min(tr[x].minn[i],tr[l].minn[i]),tr[x].maxn[i]=max(tr[x].maxn[i],tr[l].maxn[i]);

		if(r)tr[x].minn[i]=min(tr[x].minn[i],tr[r].minn[i]),tr[x].maxn[i]=max(tr[x].maxn[i],tr[r].maxn[i]);

	}

}

ll tot;

void build(ll &x,ll l,ll r,ll d){

	if(l>r)return;

	x=++tot;

	ll mid=l+r>>1;

	D=d;nth_element(p+l,p+mid,p+r+1);

	tr[x].c=p[mid];

	build(ls[x],l,mid-1,d^1);

	build(rs[x],mid+1,r,d^1);

	pushup(x);

}

inline ll abs(ll a){return a>0?a:-a;}

ll dis(point a,point b){return (a.x[0]-b.x[0])*(a.x[0]-b.x[0])+(a.x[1]-b.x[1])*(a.x[1]-b.x[1]);}

ll dissqr(point top,ll a){

	ll di=0;

	for(int i=0;i<=1;++i){

		ll nd=0;

		if(top.x[i]<tr[a].minn[i])

			nd=tr[a].maxn[i]-top.x[i];

		else if(top.x[i]>tr[a].maxn[i])

			nd=top.x[i]-tr[a].minn[i];

		else nd=max(top.x[i]-tr[a].minn[i],tr[a].maxn[i]-top.x[i]);

		di+=nd*nd;

	}

	return di;

}

void query(ll x,point top){

	ll di=dis(tr[x].c,top);

	if(di>q.top())q.pop(),q.push(di);

	ll l=ls[x],r=rs[x],dl,dr;

	dl=l?dissqr(top,l):-inf,dr=r?dissqr(top,r):-inf;

	if(dl>dr){

		if(dl>q.top())query(l,top);

		if(dr>q.top())query(r,top);

	}

	else{

		if(dr>q.top())query(r,top);

		if(dl>q.top())query(l,top);

	}

}

int main(){

	n=read(),k=read();

	for(int i=1;i<=n;++i)p[i].x[0]=read(),p[i].x[1]=read();

	build(rt,1,n,0);

	for(int i=1;i<=k+k;++i)q.push(0);

	for(int i=1;i<=n;++i)query(rt,p[i]);

	printf("%lld\n",q.top());

	return 0;

}

讲了一下kdt的重构等，也没多少啊qwq，留几个题吧

\(Luogu-P2479\)

\(Luogu-P4357\)

\(Luogu-P4475\)

\(Luogu-P4169\)

\(Luogu-P4390\)

\(Luogu-P4148\)

\(Luogu-P3769\)

够了不qwq

巴特西

K-DTree入门

例题：\(K\)远点对#

最新文章

热门文章