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上，类似时间序列分治算法。
一个例题
一句话题意 : 维护一个平面，支持插入一个点，求矩形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)$，还是有点慢。不过它至少是一个根号的啊!