k-DT

我n^2过2e5!

Posted by ShanLunjiaJian's Blog on March 11, 2021

k-dt(k近邻树)是一种维护\(k\)维空间中点集的数据结构。它称为k近邻树,是因为它最开始被发明就是用来求点集中到一个点最近的点。

为了避免歧义,以下用”结点”指k-dt上的点,用”点”指给出的点集中的点。应用k-dt时,一般有$n$远大于$2^k$,这里直接认为$k$是常数。

在OI中,k-dt一般维护二维空间,此时它也称为2-dt。2-dt维护一个二维空间中的点集,它的每个结点维护一个矩形,支持给出一个矩形,然后把这个矩形拆成\(O(\sqrt{n})\)个结点维护的矩形,对于\(k\)维的情况,则是拆成\(O(n^{1-\frac{1}{k}})\)个结点。这个操作称为Range query。

这类似于线段树或者BST,事实上1-dt就是BST,只不过我们认为\(k\geq 2\)。

Build

要构建一棵k-dt,我们从根开始递归,每次把点集划分成两部分,然后分别递归到两个儿子。

如果空间有k维,我们轮流选取每一维进行划分。假设当前划分第\(i\)维,那么我们找到当前结点维护的点中按第\(i\)维排序后的中位数,然后在当前结点存储这个中位数,并把剩下的点递归分给两边。当然这是Nodey的版本,Leafy的版本唯一区别就是当前结点不存储这个中位数。

Range query及其复杂度

要进行Range query,像线段树或者BST一样做就好了。这已经讲完了。

复杂度证明是说,考虑会走到的结点一定是部分包含于查询矩形的结点,容易发现这等价于被查询矩形的边界穿过的结点,所以我们可以计算一条直线穿过的结点数量。

我们把两轮划分一起考虑,经过两轮之后,当前矩形会被分成四个小矩形,并且四个小矩形中的点数都是原来的\(\frac{1}{4}\)。容易发现一条直线(矩形的边界必须横平竖直)最多穿过这四个矩形中的两个。(考虑一个”田”,如果一条直线可以穿过三个小方格,它就不是直线了)

那么我们得到一个递归式 :

\[T(n)=2T(\frac{n}{4})+O(1)\]

解一下容易知道\(T(n)=O(\sqrt{n})\)。

对于k维情况,也容易得到

\[T(n)=2^{k-1}T(\frac{n}{2^k})+O(1)\]

解一下容易知道\(T(n)=O(n^{1-\frac{1}{k}})\)。

这里放个板子吧,是 洛谷P4148 简单题 的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<stdio.h>
#include<algorithm>
using std::nth_element;

inline int max(const int x,const int y){ return x>y?x:y; }
inline int min(const int x,const int y){ return x<y?x:y; }

struct Point
{
	int x,y,val;
}p[500002];

inline bool cmpx(Point x,Point y){ return x.x<y.x; }
inline bool cmpy(Point x,Point y){ return x.y<y.y; }

struct Node
{
	int xl,xr,yl,yr,sum;
}t[1000002];

#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)

inline void push_up(int u){ t[u].sum=t[lq(u)].sum+t[rq(u)].sum; }

void build(int l,int r,int u,bool d)
{
	if(l==r)
	{
		t[u].xl=t[u].xr=p[l].x;
		t[u].yl=t[u].yr=p[l].y;
		t[u].sum=p[l].val;
		return;
	}
	int mid=(l+r)>>1;
	nth_element(p+l,p+mid,p+r+1,d?cmpx:cmpy);
	build(l,mid,lq(u),!d),build(mid+1,r,rq(u),!d);
	t[u].xl=min(t[lq(u)].xl,t[rq(u)].xl);
	t[u].yl=min(t[lq(u)].yl,t[rq(u)].yl);
	t[u].xr=max(t[lq(u)].xr,t[rq(u)].xr);
	t[u].yr=max(t[lq(u)].yr,t[rq(u)].yr);
	push_up(u);
}

int query(const int xl,const int xr,const int yl,const int yr,int u)
{
	if(xr<t[u].xl||t[u].xr<xl||yr<t[u].yl||t[u].yr<yl)
		return 0;
	if(xl<=t[u].xl&&t[u].xr<=xr&&yl<=t[u].yl&&t[u].yr<=yr)
		return t[u].sum;
	return query(xl,xr,yl,yr,lq(u))+query(xl,xr,yl,yr,rq(u));
}

int cnt;

int main()
{
	int tcnt=0,op,ans,xl,yl,xr,yr,lastans=0;
	scanf("%d",&op);
	while(1)
	{
		scanf("%d",&op);
		if(op==1)
		{
			cnt++,tcnt++;
			scanf("%d",&p[cnt].x),p[cnt].x^=lastans;
			scanf("%d",&p[cnt].y),p[cnt].y^=lastans;
			scanf("%d",&p[cnt].val),p[cnt].val^=lastans;
			if(tcnt>1000) build(1,cnt,1,0),tcnt=0;
		}
		else if(op==2)
		{
			scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
			xl^=lastans,yl^=lastans,xr^=lastans,yr^=lastans;
			ans=0;
			for(int i=cnt-tcnt+1;i<=cnt;i++)
				if(xl<=p[i].x&&p[i].x<=xr&&yl<=p[i].y&&p[i].y<=yr)
					ans+=p[i].val;
			printf("%d\n",(lastans=(ans+query(xl,xr,yl,yr,1))));
		}
		else break;
	}
}

插入删除,替罪羊式重构和根号重构

如果要支持插入删除,最理想的方法当然是离线下来建树,然后每次插入就激活一个点,删除就是取消激活。这样复杂度不会变。

不过有些毒瘤出题人让你强制在线,这时候一个主流做法是进行替罪羊式的重构,但是这玩意复杂度会变高……

考虑刚才的复杂度分析,如果是在一棵替罪羊2-dt上,划分两层之后在最不平衡的情况下,四个矩形的大小是\(\alpha^2:\alpha(1-\alpha):\alpha(1-\alpha):(1-\alpha)^2\),那么我们的递归式就变成了

\[T(n)=T(\alpha^2n)+T(\alpha(1-\alpha)n)+O(1)\]

这个式子我不会解通解,但是如果知道\(\alpha\)可以进行牛迭求解,根据\(\text{c}\color{red}{\text{ommand_block}}\)的说法,\(\alpha=0.75\)时解是\(T(n)\approx O(n^{0.68})\),\(\alpha=0.6\)时是\(T(n)\approx O(n^{0.57})\)。

另一个常见的做法是根号重构,或者有些人称为定期重构。

假设点数和操作数同阶,考虑如果我们每\(T\)次操作重构一次,那么全局重构总复杂度是\(O(\frac{n\log n}{T})\),操作总复杂度是\(O(n(T+\sqrt{n}))\)(零散点单独处理),容易发现\(T=\Theta(\sqrt{n\log n})\)时平衡,此时总复杂度就是\(O(n\sqrt{n\log n})\)。

还有一个更厉害的做法,我们建立两个k-dt,零散点数量达到\(\Theta(n^{\frac{1}{2}})\)时重构进第一个k-dt,第一个k-dt大小达到\(\Theta(n^{\frac{3}{4}})\)时重构进第二个k-dt,那么复杂度就是\(O(n\sqrt{n}+n^\frac{5}{4}\log n)=O(n\sqrt{n})\),常数不小但是确实快一些。

考虑k-dt效率的时候需要注意一个问题 : 重构是紧的,而查询很松。

玄学剪枝

k-dt发明出来是为了查询高维空间最近点,但是众所周知k-dt查最近点复杂度是错的……不过它确实跑的飞快。

找最近点可以考虑最优性剪枝,我们维护当前的最近点到查询点的距离\(d\),如果当前结点的矩形和 查询点为圆心\(d\)为半径的圆 没有交,就可以直接返回。随机数据表现非常优秀。

如果要构造数据卡这个算法,可以在一个圆上撒很多点,那么这些点很容易都被遍历到。

我们有几个简单的玄学策略,可能可以多水一点分(

建树的时候胡乱选取当前划分的维度,比如选择方差最大的,选择最长的,或者直接随机选择。这会让树高变成不严格的,不过反正复杂度都是错的了,树高严格有啥用?

启发式,或者随机选择先进入哪个子树。

实际上,在赛场上,遇到类似于最近点的题目,如果可以设计最优性剪枝,k-dt水分是非常有效的。当然前提是OI赛制,没有subtask并且出题人不是数据结构毒瘤。

另外对于一些k-dt复杂度正确的问题,剪枝力度也直接影响着k-dt的常数大小,比如lxl说过,k-dt查矩形sum很慢,但是矩形min/max很快。

注意在非常高的维度中,k-dt会彻底失败,比如 noi2021 量子通信,因为它是带一个\(2^k\)的常数的。我太疼了啊!

k-dt分治

线段树能做的很多东西k-dt也可以。

实际上就是有一堆贡献是矩形的东西,我们就可以对查询建立k-dt,然后把矩形们扔到k-dt上,类似时间序列分治算法。

一个例题

洛谷P4848 崂山白花蛇草水

一句话题意 : 维护一个平面,支持插入一个点,求矩形kth。

太经典了!这个题有非常奇妙的做法。

考虑最简单的方法当然是k-dt套线段树然后拆出矩形多树二分,但是这个做法复杂度是$O(\sqrt{n}\log v)$并且严格慢于树套树,没法跑过1e5。

你发现问题出在,线段树是比较紧的,而k-dt是很松的,所以我们可以改为外层值域线段树内层k-dt,然后每次二分都在较小儿子的k-dt上查,这样卡卡常就可以跑过了。

不过我们不能止步于此!实际上上面第二个做法复杂度确实有些改进,考虑如果每次二分都递归进入较大儿子,那么我们就相当于把所有没有成为答案的点查了一遍,这一共是$\log v$次查询,查询的点数加起来是$n$,所以根据琴生不等式,复杂度是$O(\sqrt{n/\log v}\log v)=O(\sqrt{n\log v})$。

是不是有更棒的方法呢?考虑如果我们使用的不是动态开点线段树而是重量平衡树,那么每次走一步子树大小至少会乘一个$\alpha$,复杂度就是

\[O(\sqrt{n}+\sqrt{\alpha n}+...)=O(\sqrt{n}(\sqrt{\alpha}+\sqrt{\alpha}^2+...))=O(\sqrt{n})\]

所以如果使用替罪羊树套k-dt,就可以做到一个根号的操作复杂度。那么考虑重构复杂度,对于替罪羊树,单次重构是$O(n\log n)$,重构子树就是$O(n\log^2 n)$,总的就是$O(n\log^3 n)$,好像有点慢。对于所有k-dt,每次插入会插进$\log$棵,但是由于那个$\alpha$,粗略分析是$O(n^{\frac{5}{4}}\log n)$,还是有点慢。不过它至少是一个根号的啊!