K-D Tree

0.前言

K-D Tree 是一种能够处理高维空间信息的数据结构，其在一些情况下能够代替 CDQ 分治以及树套树，较优秀地处理 \(k\) 维空间上的信息。

参考资料：OI-wiki

题单：\(\tt{Link}\)

1.KDT 的原理

KDT 的结构与 BST 类似，其每一个非叶子节点都具有超平面的作用，建树时会选择 \(k\) 维中某一维的值作为基准，将空间分割为两个半空间。KDT 上一个节点及其子树所形成的是一个 \(k\) 维长方体，子树中的每个点都在这个长方体内。非叶子节点的左儿子子树中的点均在超平面的左边，右儿子子树中的点均在超平面的右边。

2.KDT 建树

KDT 的建树过程可以看做不断地选择轴用以垂直分割面，然后分别递归到左子树与右子树进行再次选择、递归，而由于应当选择哪一维我们并不确定，选择哪个节点作为父节点也不确定，KDT 的形态结构与时间复杂度正确性就难以保证。
最优情况下，我们会这样建树而使得建出来的 KDT 更加平衡，树高更接近于 \(\log n\)：首先轮流选择每一维作为轴垂直分割面，然后取这一维上的中位数为分割点，分割出左右子树。这样建树的时间复杂度为 \(\mathcal{O(n \log n)}\)，而对于选择出中位数方式，可以采用 nth_element 函数。

il void build(int &u,int l,int r,int d = 0) {
    int mid = l + r >> 1;
    nth_element(b + l,b + mid,b + r + 1,[d](int x,int y) { return tr[x].x[d] < tr[y].x[d]; });
    u = b[mid];
    if (l < mid) build(tr[u].l,l,mid - 1,(d + 1) % 3);
    if (mid < r) build(tr[u].r,mid + 1,r,(d + 1) % 3);
    pushup(u);
    return ;
}

3.在 KDT 上插入节点：二进制分组重构

我们对插入进来的节点维护最多 \(\log n\) 棵 KDT，每棵的大小均为 \(2^{c}(c \in \mathbb{N})\)，每当有相同大小的 KDT，就直接将其拍扁为序列重构，合并为大小为 \(2^{c + 1}\) 的 KDT。这样进行二进制分组，插入节点的均摊时间复杂度就为 \(\mathcal{O(n \log^2 n)}\)。而在询问的时候，将 \(\log n\) 棵树的信息依次询问出来合并即可。

拍扁：

il void append(int &p) {
    if (!p) return ;
    b[++ tot] = p;
    append(tr[p].l); append(tr[p].r);
    return p = 0,void();
}

重构：

tr[++ idx] = {{x,y},w};
b[tot = 1] = idx;
for (int siz = 0; ; ++ siz )
    if (!rt[siz]) { build(rt[siz],1,tot); break; }
    else append(rt[siz]);

4.KDT 上查询信息

通常题目会要求询问一个 \(k\) 维长方体内的某种信息，我们可以类似线段树一样的对 KDT 维护一些东西：当前节点子树所维护的 \(k\) 维长方体在 \(k\) 维上坐标的区间，以及询问的答案信息。可以像线段树一样写一个 pushup 函数，合并左右儿子节点的信息到当前节点上。

这样维护之后，每次查询就能判断当前节点及其子树所维护的区间：

1. 被包含在查询区间中；
2. 与查询区间没有交集；
3. 与查询区间有交集但不被包含。

从而递归合并信息。这样的时间复杂度为 \(\mathcal{O(n^{1 - \frac{1}{k}})}\)，不会证明，如果对证明有兴趣的读者可转至 OI-wiki。

il int query(int u) {
    if (!u) return 0;
    bool fl = 0;
    rep(k,0,1) fl |= (!(L.x[k] <= tr[u].mn[k] && tr[u].mx[k] <= R.x[k]));
    if (!fl) return tr[u].s;
    rep(k,0,1) if (R.x[k] < tr[u].mn[k] || tr[u].mx[k] < L.x[k]) return 0;
    fl = 0; int ret = 0;
    rep(k,0,1) fl |= (!(L.x[k] <= tr[u].x[k] && tr[u].x[k] <= R.x[k]));
    if (!fl) ret = tr[u].val;
    return ret += query(tr[u].l) + query(tr[u].r);
}

5.KDT 的最近邻搜索

最近邻搜索即在空间中寻找最近点对。同样也可以做到最远，以及扩展到第 \(k\) 近/远。

其过程如下：

1. 因为 KDT 中每个节点都是空间中的一个点，我们先合并当前点的信息；
2. 采用启发式搜索的方式，计算出询问的点到当前点的左子树维护的长方体和右子树维护的长方体的最近/远距离；
3. 判断是否比当前最优点更加优秀，分别递归到左右子树中去查找，这里还有一个优化方式：对于左右子树，优先去更优秀的子树中查找，查找完毕后，判断另一个子树的值（即 2. 中提到的最近/远距离）是否比当前最优点更优，决定是否进入子树查找。

注意：这样的时间复杂度其实并不正确，最坏时间复杂度是 \(\mathcal{O(nq)}\) 的，\(q\) 是询问次数。

6.KDT 练习题单

\(\tt{Link}\)

这里收录了一些 KDT 的典题、好题。