K-D Tree

K-D Tree 是一种可以 高效维护 k 维空间信息 的数据结构。

K-D Tree 能够维护 k 维空间 n 个点的信息，是平衡二叉树，树上每个节点对应 k 维空间内的一个点。

为何需要 K-D Tree

信息竞赛中 $k$ 往往取 $2$ 或 $3$ , 解决二维（三维）数点问题。

二位平面数点问题，CDQ 和 树套树可以做，但是 CDQ 要求离线，树套树 常数大、空间大。当题目中要求在线、空间限制小，K-D Tree 就是最佳方法，编码难度和思维难度也适合算法竞赛。

1. 静态建树

K-D Tree 本质就是二叉搜索树(平衡的)，每个节点对应 $k$ 维空间内一个点，这个点对应的子树就是一个 $k$ 维超长方体，子树内所有点都在这个超长方体内。

K-D Tree 采用交替建树或方差建树两种方式。

• 交替建树

  所谓的交替建树 ，就是建树的时候依次选择 $k$ 维中的 $1$ 个维度，以这个维度进行排序，选择在此维度下的中位数作为本层的根，将点集分成两部分，再递归创建左右子树，递归下去的子树换到下一个维度。如果 $k=2$ ,那么当前层选择 x 作为排序标准，下一层就是 y ，接下来又是 x ,以此类推。

如果已经知道 $k$ 维空间内 $n$ 个不同的点的坐标(静态)，构建一颗 K-D Tree ,基本过程如下：

• (1). 如果当前超立方体内只有一个点，直接返回当前点。

• (2). 按照一个维度，找到当前超长方体的中位数，将空间划分成两个部分。中位数对应点就是当前空间的根节点。

• (3).切换下一个维度，递归创建左树、右树。

• (4).根据左右树信息，更新当前根节点信息，更新后放回根节点。

  以 $k=2$ 为例，举例说明：

  给定二维平面点集 ${(5,5),(7,1),(3,6),(2,1),(6,3),(8,6),(9,2)}$, 构建 K-D 树。

选择当前维度，如何高效找到中位数？如果直接 $sort$ ,那么复杂度就是 $T(n)=2T(\frac{n}{2})+n\log{n}$ ，对应建树复杂度是 $O(n\log^2{n})$。

实际存在单次 $O(n)$ 的做法，单次找出 $n$ 个元素中的中位数并将中位数置于排序后正确的位置。本质就是利用快排的思想，$O(n)$ 找第 $k$ 大?

algorithm 给提供了函数 nth_element(s+l,s+mid,s+r+1,cmp) ,可以在 $O(n)$ 复杂度内， $s[l]$ 和 $s[r]$ 之间的值按照排序规则 cmp 排序后在 $s[mid]$ 位置上的值，并保证 $s[mid]$ 左边的值小于 $s[mid]$，右边的值大于 $s[mid]$.

• 这样建树的时间复杂度就是 $T(n)=2T(\frac{n}{2})+n$ ,即 $O(n\log{n})$.

建树的参考代码如下：

bool cmpx(KD a,KD b)
{
    return a.x<b.x;
}
bool cmpy(KD a,KD b)
{
    return a.y<b.y;
}
int build(int l,int r,int k)
{
    if(l>r)return 0;
    //交叉建树    
  
    if(k==0)
        nth_element(t+l,t+mid,t+r+1,cmpx);
    else 
        nth_element(t+l,t+mid,t+r+1,cmpy);
    
    ls[mid]=build(l,mid-1,k^1);
    rs[mid]=build(mid+1,r,k^1);
    pushup(mid);  //mid 是根
    return mid;
}

• 方差建树

  可以优先选择方差大 的为排序标准建树，每次计算以下不同维度的方差。

  参考代码如下：

  int build(int l,int r)
 {
    if(l>r)return 0;
    
    int mid=(l+r)>>1;
    //按照方差大的建树
    double avx=0,avy=0,vax=0,vay=0;
    for(int i=l;i<=r;i++)avx+=t[i].x,avy+=t[i].y;
    avx/=(r-l+1); avy/=(r-l+1);  //平均值

    for(int i=l;i<=r;i++)  //方差
        vax+=(t[i].x-avx)*(t[i].x-avx),vay+=(t[i].y-avy)*(t[i].y-avy);

    if(vax>=vay)
        nth_element(t+l,t+mid,t+r+1,cmpx);
    else 
        nth_element(t+l,t+mid,t+r+1,cmpy);
    
    ls[mid]=build(l,mid-1);
    rs[mid]=build(mid+1,r);
    pushup(mid);  //mid 是根
    return mid;
 }

对于多维空间，坐标可以使用数组表示。

k 维的情况：

int build(int l,int r,int type)
{
    if(l>r)return 0;
    int mid=l+r>>1;
    nth_element(tem+l,tem+mid,tem+r+1,
        [type](int a,int b){return t[a].x[type]<t[b].x[type];});   //交叉建树
    
    int x=tem[mid];   //x是根节点
    t[x].ls=build(l,mid-1,(type+1)%k);
    t[x].rs=build(mid+1,r,(type+1)%k);
    
    pushup(x);
    return x;    
}

2.高维空间查询

在查询 k 维矩形区域内所有点的信息时，记录当前子树内每一维度上坐标的最大值和最小值。 利用这个最大值和最小值，就可以快速判断查询矩形 是否与当前子树没有交点、完全覆盖当前子树所有节点、交叉。

如果没有交点，直接返回，不在子树内查询; 如果完全覆盖，直接返回子树内所有点的信息总和（如权值和）；否则，判断当前根节点是否在查询区域内（如果不在就是 0），递归查询左、右子树，将三者的和返回。

k 维度查询的参考代码：

ll query(int p)  //询问
{
    if(p==0)return 0;

    pushdown(p);

    //不相关
    for(int i=0;i<k;i++)
        if(t[p].Min[i]>R[i]||t[p].Max[i]<L[i])return 0;
    
    //p被完全覆盖
    bool flag=true;
    for(int i=0;i<k;i++)
        if(L[i]<=t[p].Min[i] && t[p].Max[i]<=R[i])flag=true;
        else {
            flag=false;break;
        }
    if(flag)return t[p].sum;

    //有交叉
    ll ret=0;
    flag=true;
    for(int i=0;i<k;i++)
        if(L[i]<=t[p].x[i] && t[p].x[i]<=R[i])flag=true;
        else {
            flag=false; break;
        }
    if(flag)ret=t[p].v;
    return ret+query(lc)+query(rc);    
}

查询复杂度分析

严谨的分析要分情况讨论，我们选择其中一种进行分析：

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

利用迭代或者主定理，可以得到时间复杂度为 $O(\sqrt(n))$.

将递归推广到 $k$ 维，即 $T(n)=2^{k-1}T(\frac{n}{2^k})+O(1)$ ，可以得到 $T(n)=O(n^{1-\frac{1}{k}})$

3.动态建树

当需要维护的点集合时不断改变的，即会插入或者删除一些点，此时 K-D Tree 无法保持平衡，常见存在三种方式：1. 替罪羊 2. 根号重构 3. 二进制分组。

替罪羊树结构，就是设定一个不平衡因子 $a=0.75$ ,当左右子树最大值超过当前子树平衡因子，那就将整个子树拍平重构 KD Tree 采用替罪羊树，高度不是严格 $\log{n}+1$ ,查询复杂无法保证，所以这里不再介绍这种方式。

二进制分组，能够保证时间复杂度，这里重点学习这种方式。

二进制分组建树

可以维护若干棵 K-D Tree ，第 $i$ 棵树存 $2^i$ ,这些树的大小之和等于 $n$ 。$2^0+2^1+\dots+2^i \ge n$ ，$i = \log(n)+1$ 。

每颗树，需要存下根节点,使用 rt[i] 表示子树 $i$ 的根。

每次插入一个点时，从 $i=0$ 棵树判断，如果已经存在，那么 $i$ 这棵子树所有信息拍平，暴力取出来存入临时数组，直到 $i$ 这棵子树不存在，即 rt[i]=0 ,那么将之前的临时节点全部构建到 $rt[i]$ 内。

二进制分组复杂度分析

总共有 $O(\log{n})$ 棵树，建树复杂度均摊 $O(n\log^2{n})$，因为重构本身带 $log$

查询的时候，分别要到每棵树上查询，总时间复杂度为 $O(\sum_{i \ge 0}(\frac{n}{2^i})^{1-\frac{1}{k}})=O(n^{1-\frac{1}{k}})$ ，当 $k=2$ 时,查询复杂度为 $O(\sqrt{n})$.

例1. P4148 简单题

【题意简化】在一个初始值全为 $0$ 的 $n\times n$ 的二维矩阵上，进行 $q$ 次操作，每次操作为以下两种之一：

• 1 x y A：将坐标 $(x,y)$ 上的数加上 $A$．
• 2 x1 y1 x2 y2：输出以 $(𝑥1,𝑦1)$ 为左下角，$(x2,y2)$ 为右上角的矩形内（包括矩形边界）的数字和． 强制在线．内存限制 $20M$．保证答案及所有过程量在 int 范围内．$1 ≤𝑛 ≤500000,1 ≤𝑞 ≤200000$

【分析】二维平面内，动态维护单点修改，区间查询。

$20M$ 空间限制卡掉了所有树套树，强制在线卡掉了 $CDQ$ 分治，只能使用 K-D Tree .下面时采用二进制分组的参考代码，为了方便理解，本题在二维平面，参考代码中将 $x,y$ 分开写。

【参考代码】点击

例2. P14312 【模板】K-D Tree

【题意简化】要求强制在线，动态维护 k 维空间以下操作：

1. 单点插入
2. 区域内所有点点权增加 v
3. 询问区域内所有点点权之和

特殊的限制：$32M/5s$，强制在线。

【分析】本题涉及到区间修改，增加 lazy 就可以了。$k$ 维空间，坐标使用数组表示，每一维度维护好子树内最大值和最小值。

【参考代码】点击

---

领域查询

【Warning】 使用 k-D Tree 单次查询最近点的时间复杂度最坏还是 $𝑂(𝑛)$ 的，但不失为一种优秀的骗分算法，使用时请注意．在这里对邻域查询的讲解仅限于加强对 K-D Tree 结构的认识．

例3. P1429 平面最近点对（加强版）

【题意简化】 给定平面上的 $n$ 个点 $(x_i,y_i)$，找出平面上最近两个点对之间的 欧几里得距离． $2 ≤𝑛 ≤200000,0 ≤𝑥_i,𝑦_i ≤10^9$

【分析】首先 $n$ 个点坐标给定，可以先创立 K-D Tree.

然后枚举每个点到其他点的最近距离，每次暴力遍历 2-D Tree 上的每个结点的时间复杂度是 $𝑂(𝑛)$ 的，需要剪枝．我们可以维护一个子树中的所有结点在每一维上的坐标的最小值和最大值．假设当前已经找到的最近点对的距离是 $ans$，如果查询点到子树内所有点都包含在内的长方形的 最近 距离大于等于 $𝑎𝑛𝑠$，则在这个子树内一定没有答案，搜索时不进入这个子树．

此外，还可以使用一种启发式搜索的方法，即若一个结点的两个子树都有可能包含答案，先在与查询点距离最近的一个子树中搜索答案(优先搜索近的子树)．可以认为，查询点到子树对应的长方形的最近距离就是此题的估价函数．

【参考代码】交叉建树代码、方差建树代码

升级版本P7883 平面最近点对（加强加强版）

【K-D Tree 骗分卡常代码】方差卡常通过、交叉TLE2pts

本题正确做法：分治

K-D Tree 时间复杂度

由于网上大量教程和博客，在 K-D Tree 时间复杂度上有错误，这里将 K-D Tree 时间复杂度整理如下：

操作	时间复杂度
静态建树	$O(n\log{n})$
领域查询	最坏 $O(n)$
区域查询	$O(\sqrt{n})$
二进制插入重建	$O(\log^2{n})$
删除	$O(\log{n})$

参考文献

• 1. Complexity_Analysis_of_2D_KD

---

其他例题

1. P4390 [BalkanOI 2007] Mokia 摩基亚

2. P4475 巧克力王国

3. P4357 [CQOI2016] K 远点对

4. P2479 [SDOI2010] 捉迷藏

5. P2093 [国家集训队] JZPFAR

6. P3769 [CH弱省胡策R2] TATT

---

学习完毕

{{ select(1) }}

• YES
• NO