K-D Tree

簡(jiǎn)介

K-D Tree 是一種能夠維護(hù)多維數(shù)據(jù)的二叉樹(shù)。一般來(lái)說(shuō)，競(jìng)賽中用到的都是 2-D Tree，即維護(hù)二維數(shù)據(jù)，比如平面上的點(diǎn)的數(shù)據(jù)。

K-D Tree 能解決的問(wèn)題用很多其他的數(shù)據(jù)結(jié)構(gòu)也能解決，比如 CDQ 分治、樹(shù)套樹(shù)，抑或是一些計(jì)算幾何知識(shí)。因?yàn)?K-D Tree 在 \(n\gg2^k\) 有較好的時(shí)間效率，且其好寫(xiě)好調(diào)、支持在線、空間消耗小，所以也是解決部分問(wèn)題的專(zhuān)有手段。

但需要注意的是，K-D Tree 的復(fù)雜度是依賴(lài)于數(shù)據(jù)的。換句話(huà)說(shuō)，它在極端情況下其實(shí)能被構(gòu)造數(shù)據(jù)卡掉。只是目前卡它的人不多，所以它大多數(shù)時(shí)候都被用作一種較好的騙分手段。

靜態(tài)建樹(shù)

這種情況建立在所有的點(diǎn)都預(yù)先給定，然后我們需要把它們建成一棵 K-D Tree。

我們顯然希望這棵 K-D Tree 盡可能是平衡的，即樹(shù)高為 \(\log n\)。又因?yàn)樗S護(hù)二維的數(shù)據(jù)，所以我們盡可能讓當(dāng)前維度坐標(biāo)的中位數(shù)為根。具體而言，步驟為：

第一次劃分，找到所有點(diǎn)的 \(x\) 坐標(biāo)的中位數(shù)作為當(dāng)前根節(jié)點(diǎn)，分為左右兩部分；
第二次劃分，將左右兩部分再按照 \(y\) 坐標(biāo)的中位數(shù)作為當(dāng)前根節(jié)點(diǎn)，繼續(xù)遞歸；
第三次劃分，將每個(gè)部分再找到 \(x\) 坐標(biāo)的中位數(shù)作為根節(jié)點(diǎn)，再遞歸下去。

以此類(lèi)推，直到建樹(shù)完成?？傊凑?\(x\) 和 \(y\) 坐標(biāo)的中值交替建樹(shù)。

至于找出某一維度的中位數(shù)，這里我們合理使用 STL 中的 nth_element 函數(shù)即可。總建樹(shù)復(fù)雜度為 \(O(N\log N)\)。

void build(int d,int s,int t,int&p){
    if(s>t) return p=0,void();
    int mid=(s+t)>>1;
    nth_element(a+s,a+mid,a+t+1,[d](const Node&x,const Node&y){
        return x.v[d]<y.v[d];
    });
    p=++tot;
    st[p].v[0]=a[mid].v[0],st[p].v[1]=a[mid].v[1];
    build(d^1,s,mid-1,lp);
    build(d^1,mid+1,t,rp);
    pushup(p);
}

這里的 pushup 與一般的平衡樹(shù)是類(lèi)似的，都是用來(lái)維護(hù)子樹(shù)信息。一般來(lái)說(shuō) K-D Tree 的一個(gè)節(jié)點(diǎn)都需要維護(hù)當(dāng)前節(jié)點(diǎn)的最小/最大的 \(x\) 和 \(y\) 坐標(biāo)。

動(dòng)態(tài)建樹(shù)

動(dòng)態(tài)建樹(shù)一般有根號(hào)重構(gòu)和二進(jìn)制分組兩種方式，一般二進(jìn)制分組會(huì)快一些。

我們維護(hù)若干棵大小為 \(2^i\) 的 K-D Tree，滿(mǎn)足這些樹(shù)的大小之和為 \(n\)。每插入的時(shí)候，就新增一棵大小為 \(2^0\) 的 K-D Tree，然后不斷地向上合并。實(shí)際實(shí)現(xiàn)的時(shí)候可以先將合并在一起的樹(shù)拍扁，然后只需重構(gòu)一次即可。復(fù)雜度均攤 \(O(n\log^2n)\)。

struct{
	#define lp st[p].lc
	#define rp st[p].rc
	struct KDT{
		int lc,rc,v[2],mx[2],mn[2];
	}st[MAXN];
	int tot,used[MAXN],pt;
	void del(int&p){
		used[++pt]=p;
		st[p]={0,0,0,0,0,0,0,0};
		p=0;
	}
	int newnode(){
		return pt?used[pt--]:++tot;
	}
	void pushup(int p){
		for(int i=0;i<2;i++){
			st[p].mx[i]=st[p].mn[i]=st[p].v[i];
			if(lp){
				st[p].mx[i]=max(st[p].mx[i],st[lp].mx[i]);
				st[p].mn[i]=min(st[p].mn[i],st[lp].mn[i]);
			}
			if(rp){
				st[p].mx[i]=max(st[p].mx[i],st[rp].mx[i]);
				st[p].mn[i]=min(st[p].mn[i],st[rp].mn[i]);
			}
		}
	}
	void build(int d,int s,int t,int&p){
		if(s>t) return;
		int mid=(s+t)>>1;
		nth_element(a+s,a+mid,a+t+1,[d](const Node&x,const Node&y){
			return x.v[d]<y.v[d];
		});
		p=newnode();
		st[p].v[0]=a[mid].v[0],st[p].v[1]=a[mid].v[1];
		build(d^1,s,mid-1,lp);
		build(d^1,mid+1,t,rp);
		pushup(p);
	}
	void redo(int&p){
		if(!p) return;
		a[++cnt]={st[p].v[0],st[p].v[1]};
		redo(lp),redo(rp);
		del(p);
	}
	void ins(int x,int y){
		a[cnt=1]={x,y};
		for(int i=0;i<=F;i++){
			if(!rt[i]){
				build(0,1,cnt,rt[i]);
				break;
			}else redo(rt[i]);
		}
	}
    // 以上為插入部分函數(shù)
}T;

實(shí)際插入的時(shí)候調(diào)用 \(\operatorname{ins}(x,y)\) 即可。注意，二進(jìn)制分組的組數(shù)（即代碼中的 F）是等于 \(\log(\text{點(diǎn)數(shù)})\) 的。

查詢(xún)操作

矩陣查詢(xún)

這種查詢(xún)方式一般要求查詢(xún)一個(gè)矩陣范圍內(nèi)的點(diǎn)的相關(guān)信息。具體實(shí)現(xiàn)上，在遞歸途中，如果目標(biāo)矩形和當(dāng)前矩形無(wú)交點(diǎn)，則跳出；如果當(dāng)前矩形被目標(biāo)矩形完全包含，則直接返回當(dāng)前信息；否則先判斷當(dāng)前矩形是否合法，然后繼續(xù)遞歸搜索。

可以證明這樣做的復(fù)雜度是 \(O(n^{1-1/k})\) 的。對(duì)于常見(jiàn)的 2-D Tree，那就是 \(O(n\sqrt n)\)。

典型例題：P4475 巧克力王國(guó)。

將每塊巧克力看成在二維平面上的一個(gè)點(diǎn)，坐標(biāo) \((x,y)\)，點(diǎn)權(quán)為 \(h\)。建出 K-D Tree 后，維護(hù) K-D Tree 上每個(gè)節(jié)點(diǎn)的坐標(biāo)最大/最小值。對(duì)于每次查詢(xún)，代入系數(shù) \(a,b\) 進(jìn)行計(jì)算，對(duì)于當(dāng)前節(jié)點(diǎn)維護(hù)的坐標(biāo)極值分別算出答案判斷是否小于 \(c\)，然后再使用上文的判斷方法繼續(xù)遞歸即可。

實(shí)際上，這題并不是嚴(yán)格意義上的矩陣查詢(xún)，所以它的復(fù)雜度是由隨機(jī)數(shù)據(jù)保證的。

核心代碼如下：

using ll=long long;
constexpr int MAXN=50005;
int n,m,rt;
ll A,B,C;
struct Node{
	int v[2],vl;
}a[MAXN];
struct{
	#define lp st[p].lc
	#define rp st[p].rc
	struct KDT{
		int lc,rc,v[2],mx[2],mn[2];
		ll sm,vl;
	}st[MAXN];
	int tot;
	void pushup(int p){
		st[p].sm=st[lp].sm+st[rp].sm+st[p].vl;
		for(int i=0;i<2;i++){
			st[p].mx[i]=st[p].mn[i]=st[p].v[i];
			if(lp){
				st[p].mx[i]=max(st[p].mx[i],st[lp].mx[i]);
				st[p].mn[i]=min(st[p].mn[i],st[lp].mn[i]);
			}
			if(rp){
				st[p].mx[i]=max(st[p].mx[i],st[rp].mx[i]);
				st[p].mn[i]=min(st[p].mn[i],st[rp].mn[i]);
			}
		}
	}
	void build(int d,int s,int t,int&p){
		if(s>t) return p=0,void();
		int mid=(s+t)>>1;
		nth_element(a+s,a+mid,a+t+1,[d](const Node&x,const Node&y){
			return x.v[d]<y.v[d];
		});
		p=++tot;
		st[p].v[0]=a[mid].v[0],st[p].v[1]=a[mid].v[1],st[p].vl=a[mid].vl;
		build(d^1,s,mid-1,lp);
		build(d^1,mid+1,t,rp);
		pushup(p);
	}
	int chk(int p){
		int res=0;
		if(st[p].mn[0]*A+st[p].mn[1]*B<C) res++;
		if(st[p].mn[0]*A+st[p].mx[1]*B<C) res++;
		if(st[p].mx[0]*A+st[p].mn[1]*B<C) res++;
		if(st[p].mx[0]*A+st[p].mx[1]*B<C) res++;
		return res;
	}
	ll query(int p){
		switch(chk(p)){
			case 0: return 0;
			case 4: return st[p].sm;
			default:{
				ll res=0;
				if(st[p].v[0]*A+st[p].v[1]*B<C) res+=st[p].vl;
				if(lp) res+=query(lp);
				if(rp) res+=query(rp);
				return res;
			}
		}
	}
}T;

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]={read(),read(),read()};
	T.build(0,1,n,rt);
	while(m--){
		A=read(),B=read(),C=read();
		write(T.query(rt));
	}
	return fw,0;
}

鄰域查詢(xún)

這種查詢(xún)方式一般要求查詢(xún)距離一個(gè)點(diǎn)最近/最遠(yuǎn)的點(diǎn)。我們一般需要貪心地為一棵子樹(shù)設(shè)計(jì)一個(gè)估價(jià)函數(shù)，優(yōu)先往估價(jià)函數(shù)優(yōu)的一方去搜索。再加上最優(yōu)性剪枝即可。

K-D Tree 在鄰域查詢(xún)上的時(shí)間復(fù)雜度依舊是由隨機(jī)數(shù)據(jù)保證的。

典型例題：P2479 [SDOI2010] 捉迷藏。

查詢(xún)最近點(diǎn)的板子題。代碼如下：

constexpr int MAXN=1e5+5,INF=0x3f3f3f3f;
int n,rt;
struct Node{
	int v[2];
}a[MAXN];
struct{
	#define lp st[p].lc
	#define rp st[p].rc
	struct KDT{
		int lc,rc,v[2],mx[2],mn[2];
	}st[MAXN];
	int tot;
	void pushup(int p){
		for(int i=0;i<2;i++){
			st[p].mx[i]=st[p].mn[i]=st[p].v[i];
			if(lp){
				st[p].mx[i]=max(st[p].mx[i],st[lp].mx[i]);
				st[p].mn[i]=min(st[p].mn[i],st[lp].mn[i]);
			}
			if(rp){
				st[p].mx[i]=max(st[p].mx[i],st[rp].mx[i]);
				st[p].mn[i]=min(st[p].mn[i],st[rp].mn[i]);
			}
		}
	}
	void build(int d,int s,int t,int&p){
		if(s>t) return p=0,void();
		int mid=(s+t)>>1;
		nth_element(a+s,a+mid,a+t+1,[d](const Node&x,const Node&y){
			return x.v[d]<y.v[d];
		});
		p=++tot;
		st[p].v[0]=a[mid].v[0],st[p].v[1]=a[mid].v[1];
		build(d^1,s,mid-1,lp);
		build(d^1,mid+1,t,rp);
		pushup(p);
	}
	int dis(int x1,int y1,int x2,int y2){
		return abs(x1-x2)+abs(y1-y2);
	}
	int fmin(int x,int y,int p){
		int res=0;
		if(x<st[p].mn[0]) res+=st[p].mn[0]-x;
		if(x>st[p].mx[0]) res+=x-st[p].mx[0];
		if(y<st[p].mn[1]) res+=st[p].mn[1]-y;
		if(y>st[p].mx[1]) res+=y-st[p].mx[1];
		return res;
	}
	int fmax(int x,int y,int p){
		int res=0;
		res+=max(abs(x-st[p].mn[0]),abs(x-st[p].mx[0]));
		res+=max(abs(y-st[p].mn[1]),abs(y-st[p].mx[1]));
		return res;
	}
	void qmin(int&mn,int x,int y,int p){
		if(!p) return;
		if(x!=st[p].v[0]||y!=st[p].v[1]) mn=min(mn,dis(x,y,st[p].v[0],st[p].v[1]));
		int vl=INF,vr=INF;
		if(lp) vl=fmin(x,y,lp);
		if(rp) vr=fmin(x,y,rp);
		if(vl<vr){
			if(vl<mn) qmin(mn,x,y,lp);
			if(vr<mn) qmin(mn,x,y,rp);
		}else{
			if(vr<mn) qmin(mn,x,y,rp);
			if(vl<mn) qmin(mn,x,y,lp);
		}
	}
	void qmax(int&mx,int x,int y,int p){
		if(!p) return;
		if(x!=st[p].v[0]||y!=st[p].v[1]) mx=max(mx,dis(x,y,st[p].v[0],st[p].v[1]));
		int vl=-INF,vr=-INF;
		if(lp) vl=fmax(x,y,lp);
		if(rp) vr=fmax(x,y,rp);
		if(vl>vr){
			if(vl>mx) qmax(mx,x,y,lp);
			if(vr>mx) qmax(mx,x,y,rp);
		}else{
			if(vr>mx) qmax(mx,x,y,rp);
			if(vl>mx) qmax(mx,x,y,lp);
		}
	}
}T;

int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]={read(),read()};
	T.build(0,1,n,rt);
	int ans=INF;
	for(int i=1,mx,mn;i<=n;i++){
		mx=-INF,mn=INF;
		T.qmax(mx,a[i].v[0],a[i].v[1],rt);
		T.qmin(mn,a[i].v[0],a[i].v[1],rt);
		ans=min(ans,mx-mn);
	}
	printf("%d\n",ans);
	return 0;
}

posted @ 2025-05-03 16:49 Laoshan_PLUS 閱讀(44) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

laoshan-plus

K-D Tree

K-D Tree

簡(jiǎn)介

靜態(tài)建樹(shù)

動(dòng)態(tài)建樹(shù)

查詢(xún)操作

矩陣查詢(xún)

鄰域查詢(xún)

公告