K-D Tree

11490DX Re: Master Lv.15
  2025-05-08 16:39:42 2025-05-08 16:39:42 Created   2025-05-28 08:52:13 2025-05-28 08:52:13 Updated      3.2k Words  12 Mins  

 

K-D Tree 一般是处理多维偏序关系的一个数据结构。一般使用 K-D Tree 的时间复杂度有 的，也有时间复杂度未知的（就是剪枝出奇迹），总之也是比较的好用。

建树

先来看 K-D Tree 如何构造（这里以 2-D Tree 为例）：

对于这些点，它建出来的 2-D Tree 是这样的：

具体来说，我们递归建树，设当前深度为 ：

  1. 当 为偶数时，按照 坐标排序，否则按照 坐标排序。
  2. 取中间的那一个点作为这棵子树的根。定基准值为 。
  3. 取小于 的递归至左子树，大于 的递归至右子树，并且使它们的 。

对于排序，其实我们并不需要很精准的排序，就只是把小于 的放左边，大于 的放右边，这个可以使用函数 nth_element(begin, mid, end, cmp) 解决。它会帮你将 意义下的小于 的所有数全放 前面，其它的全放后面。很适合用来做建树操作，并且复杂度为 。

1
2
3
4
5
6
7
8
void build(int &x, int l, int r, int dep){
    int mid = l+r>>1;
    nth_element(b+l, b+mid, b+r+1, [dep](int x, int y){return tr[x].pos[dep] < tr[y].pos[dep];});
    x = b[mid];
    if(l < mid) build(ls(x), l, mid-1, dep^1);
    if(mid < r) build(rs(x), mid+1, r, dep^1);
    pushup(x);
}

对于其它-D，顺序类似，例如三维就是 ，四维就是 等等。

建好树了之后，就可以开始维护一些信息了。维护什么信息就根据题目的要求来定。比如说这道题：

P4148 简单题

你有一个 的棋盘，每个格子内有一个整数，初始时的时候全部为 ，现在需要维护两种操作：

  • 1 x y A ， 是正整数。将格子x,y里的数字加上 。
  • 2 x1 y1 x2 y2 ，。输出 这个矩形内的数字和。
  • 3 无，终止程序。

我们需要维护的就是区间和。那么 是肯定要有的。然后 操作就是新加点，可以看作 insert() 操作。那么现在要实现 insert() 操作和 query() 操作。

插入

那么对于插入操作，其实有两种方法。

1. 类似替罪羊树的插入操作

首先，执行插入操作。按照 遍历直到该点为 。然后将这个点赋为新点，退出。

1
2
3
4
5
6
7
8
9
10
11
inline void insert(int &x, int w, int dep){
    // cerr<<x<<'\n';
    if(x == 0){
        x = w; pushup(x); 
        return void();
    }
    if(pos(x, dep) < pos(w, dep)) insert(ls(x), w, nxt(dep));
    else insert(rs(x), w, nxt(dep));
    pushup(x);
    maintain(x, dep);
}

我们维护一个 。同时定义一个平衡因子 。当 时，区间拍平，重构这棵树。

具体来说，先中序遍历取出所有的点，然后重建。这种方法复杂度玄学。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const double alpha = 0.75;
inline void pia(int x){
    if(x == 0) return void();
    pia(ls(x)); 
    b[++blen] = x;
    pia(rs(x));
    ls(x) = rs(x) = 0;
}
inline void rebuild(int &x, int l, int r, int dep){
    int mid = l+r>>1;
    nth_element(b+l, b+mid, b+r+1, [dep](int x, int y){return pos(x, dep) < pos(y, dep);});
    x = b[mid];
    if(l < mid) rebuild(ls(x), l, mid-1, nxt(dep));
    if(mid < r) rebuild(rs(x), mid+1, r, nxt(dep));
    pushup(x);
}
void maintain(int &x, int dep){
    if(max(siz(ls(x)), siz(rs(x))) >= alpha*siz(x)){
        blen = 0;
        pia(x); rebuild(x, 1, blen, dep);
    }
}

2. 二进制分组

我们定义一个 数组。 维护的是大小为 的 K-D Tree 的根。然后新插入一个点的时候，就新建一个大小为 的树，然后找到第一个为 的 ，将前面的全部合并。因为我们插入一个数，要凑出来一个大小为 的整数次幂的大小的树，只能这么合并。这种方法复杂度稳定，恒为 。

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
void insert(int &x, int l, int r, int dep){
    int mid = l+r>>1;
    nth_element(b+l, b+mid, b+1+r, [dep](int a, int b){return tr[a].pos[dep] < tr[b].pos[dep];});
    x = b[mid];
    if(l == r) return pushup(x), void();
    if(l < mid) insert(tr[x].ls, l, mid-1, dep^1);
    if(r > mid) insert(tr[x].rs, mid+1, r, dep^1);
    pushup(x);
}
void pickup(int x){
    b[++blen] = x;
    if(tr[x].ls) pickup(tr[x].ls);
    if(tr[x].rs) pickup(tr[x].rs);
    tr[x].ls = tr[x].rs = 0;
}
...
kdt.newnode(x, y, A);
blen = 0; b[++blen] = n;
for(int i=0;i<=L;i++){
    if(rt[i] == 0){
        kdt.insert(rt[i], 1, blen, 0);
        break;
    }else{
        kdt.pickup(rt[i]);
        rt[i] = 0;
    }
}

查询

插入搞完了之后，就开始查询。查询的方法应按照题目的要求来优化。以这道题为例，要查询一个矩形区间的所有点权和。我们假设以第一种插入方法为例，这时只有一个根（第二种插入方法就把所有根全部 query 一遍即可）。

我们记录一个区间的 坐标的区间， 坐标的区间（这个区间可以在插入时 pushup 维护）。然后查询的时候就开始剪枝：

  1. 当这个点为 时，返回 ；
  2. 当这个点对应的区间在查询区间外时，返回 ；
  3. 当这个点对应的区间在查询区间内时，返回 ；
  4. 否则只能查询这个点是否在查询区间内，记录贡献后再查询左右子树，最后返回。
1
2
3
4
5
6
7
int query(int x){
    if(x == 0) return 0;
    if(isin(x)) return tr[x].sum;
    if(isout(x)) return 0;
    int re = (check(x)? tr[x].val: 0);
    return query(ls(x)) + query(rs(x)) + re;
}

双倍经验 P4390 Mas

例题

P4169 天使玩偶 Mas

题目大意

Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。

我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 ，那么她离近的天使玩偶可能埋下的地方有多远。

因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为 。其中 表示点 的横坐标，其余类似。

第一行包含两个整数 和 ，在刚开始时，Ayu 已经知道有 个点可能埋着天使玩偶， 接下来 Ayu 要进行 次操作。

接下来 行，每行两个非负整数 ，表示初始 个点的坐标。

再接下来 行，每行三个非负整数 。

  • 如果 ，则表示 Ayu 又回忆起了一个可能埋着玩偶的点 。
  • 如果 ，则表示 Ayu 询问如果她在点 ，那么在已经回忆出来的点里，离她近的那个点有多远

对于 的数据，保证 ，。

解答

这道题我们引入一个概念叫估价函数。这个函数用来评估如果访问这个子树的可能得到的最优解。比如这道题，这道题我们定一棵子树的估价函数为要查询的点离子树代表的矩形内部的最近距离。

我们就比对两个子树的估价函数值。然后先取小的那个递归下去，然后再比较递归后的答案是否大于大的那个的函数值，若是，则继续递归。同时，若现在的答案已经比两个函数值都小了，那么直接 return。

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
inline int func_dis(int x){
    // 求 qp 点在 x 的 max-min 矩形范围内的最小距离。
    if(x == 0) return 0x3f3f3f3f;
    int re = 0;
    for(int i=0;i<2;i++){
        if(qp[i] < mini(x, i)) re += mini(x, i) - qp[i];
        else if(qp[i] > maxi(x, i)) re += qp[i] - maxi(x, i);
    }
    return re;
}
int getdis(int x){
    // 求 qp 点到 x 点的曼哈顿距离
    return abs(qp[0]-tr[x].pos[0]) + abs(qp[1]-tr[x].pos[1]);
}
inline void query(int x){
    // cerr<<x<<'\n';
    if(x == 0) return ;
    ans = min(ans, getdis(x));
    int lre = func_dis(ls(x)), rre = func_dis(rs(x));
    if(lre <= rre){
        if(ans > lre) query(ls(x));
        if(ans > rre) query(rs(x));
    }else{
        if(ans > rre) query(rs(x));
        if(ans > lre) query(ls(x));
    }
}

另外提一嘴，这道题宜使用替罪羊树式插入，不宜使用二进制分组式插入。

P7883 平面最近点对 Exp 骗分法

题目大意

给定 个二维欧几里得平面上的点 ，请输出距离最近的两个点的距离的平方。

由于输入的点为整点，因此这个值一定是整数。

对于 的数据，，。

解答

依然是一个一个点的插入。依然定估价函数为要查询的点离子树代表的矩形内部的最近距离。然后骗分大法开始：

1
2
3
4
5
6
7
shuffle(b+1, b+1+n, rnd);
for(int i=1;i<=n;i++){
    if((double)clock()/CLOCKS_PER_SEC > 0.343) break;
    qp[0] = pos(b[i], 0), qp[1] = pos(b[i], 1);
    qpidx = b[i]; kdt.query(rt);
}
cout<<ans<<'\n';

P4475 巧克力王国 Mas

题目大意

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。

对于每一块巧克力，我们设 和 为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数 和 ，分别为他自己为牛奶和可可定义的权重， 因此牛奶和可可含量分别为 和 的巧克力对于他的甜味程度即为 。而每个人又有一个甜味限度 ，所有甜味程度大于等于 的巧克力他都无法接受。每块巧克力都有一个美味值 。

现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少。

对于100%的数据，,。

保证数据用某种方式随机生成。

解答

因为值有可能是负的，然后就记 和 ，在 isin() 和 isout() 函数里面坐标取 即可。

P3769 TATT Mas

题目大意

四维空间真是美妙。现在有 个四维空间中的点，请求出一条最长的路径，满足任意一维坐标都是单调不降的。

注意路径起点是任意选择的，并且路径与输入顺序无关（路径顺序不一定要满足在输入中是升序）。

路径的长度是经过的点的数量，任意点只能经过一次。

输出最长路径的长度。

解答

首先将坐标按照字典序排序，然后就是一道裸的 K-D Tree 维护三维偏序问题了。

P4848 崂山白花蛇草水 Ult

题目大意

蒟蒻 Bob 会在一个宽敞的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇 Aleph 在矩形区域 中，崂山白花蛇草水瓶数第 多的是多少。为了避免麻烦，蒟蒻 Bob 不会在同一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻 Bob 想为难一下神犇 Aleph，希望他能在每次询问时立刻回
答出答案。

询问强制在线。存在不存在第 多的瓶数的情况。

对于所有数据，，，，，，，。

解答

建立一棵权值线段树，每一个节点套一棵 K-D Tree。然后跑树上二分即可。

P6783 [Ynoi] rrusq Ult

题目大意

给定一个二维平面，有 个关键点， 个矩形，以及 个询问，每个关键点有一个权值 。

定义一个左下角为 ，右上角为 的矩形包含一个点 ，当且仅当 且 。

每次询问给定 ，对于一个关键点 ，如果点 在编号在 内的任意一个矩形中，则认为 被区间 的矩形并包含，输出区间 的矩形并包含的所有关键点的权值和。

对于 的数据，，。

，，，。

解答

那么我们就先把询问离线，然后从左往右扫描线。

设当前扫过的矩形编号为 ，我们使用 K-D Tree 维护每一个点最晚被哪个矩形包含（即被包含的矩形编号的最大值）。当一个新的矩形插入进来时，因为我们遍历 K-D Tree 的复杂度是 的，打标记的复杂度也自然就是 ，所以总共打标记的次数就是 。

然后就是查询和：查询我们可以将查询 改为查询 ，就相当于是一个后缀查询和。一共要查 次。所以我们需要一个 修改、 查询的数据结构来平衡复杂度。发现可以使用分块来维护。

  • Title: K-D Tree
  • Author: 11490DX
  • Created at : 2025-05-08 16:39:42
  • Updated at : 2025-05-28 08:52:13
  • Link: https://11490dx.net/2025/05/08/kd-tree/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
K-D Tree
  1. 建树
  2. 插入
  3. 查询
  4. 例题