k-D Tree 学习笔记
Visits: 538
k-D Tree 是一种可以高效处理 $k$ 维空间信息的数据结构,在算法竞赛的题目中一般 $k = 2$。
建树
k-D Tree 具有二叉搜索树的形态,二叉搜索树上的每个节点都对应 $k$ 维空间内的一个点。其每个子树中的点都在一个 $k$ 维的超长方体内,这个超长方体内的所有点也都在这个子树中。
假设我们已经知道了 $k$ 维空间内的 $n$ 个不同的点的坐标,要将其构建成一棵 k-D Tree,步骤如下:
- 若当前超长方体中没有点时,直接返回。
- 选择一个方差最大的维度,将当前超长方体按照这个维度分成两个超长方体。
- 选择该维度上为中位数的切割点,这一维度上的值小于这个点的归入一个超长方体(左子树),其余的归入另一个超长方体(右子树)。
- 将选择的点作为这棵子树的根节点,递归对分出的两个超长方体构建左右子树,维护子树的信息。
可以发现树高为 $\mathcal O(\log n)$,因此时间复杂度为 $\mathcal O(n \log n)$,其中第三步找中位数时需要用到 nth_element
。
插入/删除
如果维护的这个 $k$ 维点集是可变的,即可能会插入或删除一些点,此时 k-D Tree 的平衡性(树高为 $\mathcal O(\log n)$)无法保证。由于 k-D Tree 的构造,可以保证平衡性的手段只有定期重构思想。
我们引入一个重构常数 $\alpha \in (0.5,1)$,一般取 $0.75$ 左右,可以根据实际情况调整。对于 k-D Tree 上的一个节点 $x$,若其有一个子树的节点数在以 $x$ 为根的子树的节点数中的占比大于 $\alpha$,则认为以 $x$ 为根的子树是不平衡的,需要重构。重构时,先遍历子树求出一个序列,然后用以上描述的方法建出一棵 k-D Tree,代替原来不平衡的子树。
在插入一个 $k$ 维点时,先根据记录的分割维度和分割点判断应该继续插入到左子树还是右子树,如果到达了空节点,新建一个节点代替这个空节点。成功插入节点后回溯插入的过程,维护节点的信息,如果发现当前的子树不平衡,则重构当前子树。
如果还有删除操作,则使用懒惰删除,即删除一个节点时打上删除标记,而保留其在 k-D Tree 上的位置。当删除的节点数在以 $x$ 为根的子树中的占比大于 $\alpha$ 时,同样认为这个子树是不平衡的,需要重构。
邻域查询
【例题】P1429 平面最近点对(加强版)
首先建出关于这 $n$ 个点的 2-D Tree。
枚举每个节点,对于每个节点找到不等于该节点且距离最小的点,即可求出答案。每次暴力遍历 2-D Tree 上的每个节点的时间复杂度是 $\mathcal O(n)$ 的,需要剪枝。我们可以维护一个子树中的所有节点在每一维上的坐标的最小值和最大值。假设当前已经找到的最近点对的距离是 $ans$,如果查询点到子树内所有点都包含在内的长方形的最近距离大于等于 $ans$,则在这个子树内一定没有答案,搜索时不进入这个子树。
此外,若一个节点的两个子树都有可能包含答案,先在与查询点距离最近的一个子树中搜索答案。可以认为,查询点到子树对应的长方形的最近距离就是此题的估价函数。
注意:虽然以上使用的种种剪枝优化,但是使用 k-D Tree 单次查询最近点的时间复杂度最坏还是 $\mathcal O(n)$ 的,但不失为一种优秀的骗分算法,使用时请注意。在这里对邻域查询的讲解仅限于加强对 k-D Tree 结构的认识,同时提供一种尽可能多拿分的方法。
【练习】LOJ2043 「CQOI2016」K 远点对
#define pl pair<ll, ll>
const int N = 1e5 + 7;
int n, k, lc[N], rc[N];
pl p[N];
pq<ll> q;
ll L[N], R[N], D[N], U[N];
inline void upd(int x) {
L[x] = R[x] = p[x].fi, D[x] = U[x] = p[x].se;
if (lc[x])
L[x] = min(L[x], L[lc[x]]), R[x] = max(R[x], R[lc[x]]),
D[x] = min(D[x], D[lc[x]]), U[x] = max(U[x], U[lc[x]]);
if (rc[x])
L[x] = min(L[x], L[rc[x]]), R[x] = max(R[x], R[rc[x]]),
D[x] = min(D[x], D[rc[x]]), U[x] = max(U[x], U[rc[x]]);
}
#define f(x) ((x) * (x))
#define mid ((l + r) >> 1)
int build(int l, int r) {
if (l > r) return 0;
ld px = 0, py = 0, sx = 0, sy = 0;
for (int i = l; i <= r; i++) px += p[i].fi, py += p[i].se;
px /= r - l + 1, py /= r - l + 1;
for (int i = l; i <= r; i++) sx += f(px - p[i].fi), sy += f(py - p[i].se);
nth_element(p + l, p + mid, p + r + 1, [&](pl x, pl y) { return sx > sy ? x.fi < y.fi : x.se < y.se; });
return lc[mid] = build(l, mid - 1), rc[mid] = build(mid + 1, r), upd(mid), mid;
}
inline ll s(int x, int y) {
return max(f(p[x].fi - L[y]), f(p[x].fi - R[y])) + max(f(p[x].se - D[y]), f(p[x].se - U[y]));
}
void ask(int l, int r, int x) {
if (l > r) return;
ll o = f(p[x].fi - p[mid].fi) + f(p[x].se - p[mid].se);
if (o > -q.top()) q.pop(), q.push(-o);
ll sl = lc[mid] ? s(x, lc[mid]) : 0, sr = rc[mid] ? s(x, rc[mid]) : 0;
if (sl > sr) {
if (sl > -q.top()) ask(l, mid - 1, x);
if (sr > -q.top()) ask(mid + 1, r, x);
} else {
if (sr > -q.top()) ask(mid + 1, r, x);
if (sl > -q.top()) ask(l, mid - 1, x);
}
}
int main() {
rd(n, k), k <<= 1;
for (int i = 1; i <= k; i++) q.push(0);
for (int i = 1; i <= n; i++) rd(p[i].fi, p[i].se);
build(1, n);
for (int i = 1; i <= n; i++) ask(1, n, i);
print(-q.top());
return 0;
}
高维空间上的操作
【例题】P4148 简单题
$20\text{MB}$ 卡掉了树套树,强制在线卡掉了 CDQ 分治,只能考虑 k-D Tree 了。
构建 2-D Tree,支持两种操作:添加一个二维点;查询矩形区域内的所有点的权值和。
在查询矩形区域内的所有点的权值和时,仍然需要记录子树内每一维度上的坐标的最大值和最小值。如果当前子树对应的矩形与所求矩形没有交点,则不继续搜索其子树;如果当前子树对应的矩形完全包含在所求矩形内,返回当前子树内所有点的权值和;否则,判断当前点是否在所求矩形内,更新答案并递归在左右子树中查找答案。
可以证明,如果在 2-D Tree 上进行矩阵查询操作,单次查询时间复杂度最优 $\mathcal O(\log n)$,最坏 $\mathcal O(\sqrt n)$。事实上,可以将结论扩展到 $k$ 维的情况,最坏时间复杂度为 $\mathcal O(n^{1-\frac 1 k})$。
const int N = 2e5 + 7;
int n, rt, lc[N], rc[N], d[N], s[N], sum[N], L[N], R[N], D[N], U[N], ans;
struct P {
int x, y, z;
inline void in() {
rd(x, y, z), x ^= ans, y ^= ans, z ^= ans;
}
} p[N];
inline void upd(int x) {
L[x] = R[x] = p[x].x, D[x] = U[x] = p[x].y;
if (lc[x])
L[x] = min(L[x], L[lc[x]]), R[x] = max(R[x], R[lc[x]]),
D[x] = min(D[x], D[lc[x]]), U[x] = max(U[x], U[lc[x]]);
if (rc[x])
L[x] = min(L[x], L[rc[x]]), R[x] = max(R[x], R[rc[x]]),
D[x] = min(D[x], D[rc[x]]), U[x] = max(U[x], U[rc[x]]);
s[x] = s[lc[x]] + s[rc[x]] + 1;
sum[x] = sum[lc[x]] + sum[rc[x]] + p[x].z;
}
#define f(x) ((x) * (x))
#define mid ((l + r) >> 1)
int g[N], t;
int build(int l, int r) {
if (l > r) return 0;
ld px = 0, py = 0, sx = 0, sy = 0;
for (int i = l; i <= r; i++) px += p[g[i]].x, py += p[g[i]].y;
px /= r - l + 1, py /= r - l + 1;
for (int i = l; i <= r; i++) sx += f(px - p[g[i]].x), sy += f(py - p[g[i]].y);
d[g[mid]] = sx > sy ? 1 : 2;
nth_element(g + l, g + mid, g + r + 1, [&](int i, int j) { return sx > sy ? p[i].x < p[j].x : p[i].y < p[j].y; });
return lc[g[mid]] = build(l, mid - 1), rc[g[mid]] = build(mid + 1, r), upd(g[mid]), g[mid];
}
const ld alpha = 0.75;
inline bool bad(int x) {
return max(s[lc[x]], s[rc[x]]) > alpha * s[x];
}
void dfs(int x) {
if (x) dfs(lc[x]), g[++t] = x, dfs(rc[x]);
}
inline int rebuild(int x) {
return t = 0, dfs(x), build(1, t);
}
void ins(int &x, int o) {
if (!x) return upd(x = o);
if (d[x] == 1) ins(p[o].x <= p[x].x ? lc[x] : rc[x], o);
else ins(p[o].y <= p[x].y ? lc[x] : rc[x], o);
upd(x);
if (bad(x)) x = rebuild(x);
}
int lx, ly, rx, ry;
int ask(int x) {
if (!x || lx > R[x] || rx < L[x] || ly > U[x] || ry < D[x]) return 0;
if (lx <= L[x] && rx >= R[x] && ly <= D[x] && ry >= U[x]) return sum[x];
return (lx <= p[x].x && rx >= p[x].x && ly <= p[x].y && ry >= p[x].y ? p[x].z : 0) + ask(lc[x]) + ask(rc[x]);
}
int main() {
rd(n), n = 0;
while (1) {
int o;
rd(o);
if (o == 1) {
p[++n].in(), ins(rt, n);
} else if (o == 2) {
rd(lx, ly), rd(rx, ry), lx ^= ans, ly ^= ans, rx ^= ans, ry ^= ans, print(ans = ask(rt));
} else break;
}
return 0;
}
参考资料
- OI Wiki k-D Tree