K-D Tree

· · 算法·理论

模拟赛用到了,但之前写过 0 次 KDT,荣获调一整场 87pts。来训一下这个东西。

OI 里用的 K-D Tree 一般都是 2-D Tree,用来解决 4-side 矩形的修改查询问题。

建树

维护一个平面点集,每次选取长边按中位数切开,递归建树。

可以证明树高是 \log_2 n+O(1) 的。注意不能是 O(\log n),否则复杂度可能会爆。

精细实现下时间 O(n \log n),空间 O(n)。

查询 / 修改

和线段树一样,KDT 支持查询的是半群信息。单次操作复杂度 O(\sqrt{n})。

插入 / 删除

如果要在点集中插入 / 删除一些点,kdt 可能保持不了平衡,复杂度就爆了。

常用的解决方法:

实际上 OI 中取 \alpha=0.6 的替罪羊式重构一般就够用了。

其他用途

一般来说,不需要插入删除的静态 KDT 是好写的。

练习

KDT 的写法可以看代码。

P6349 [PA 2011] Kangaroos

给出 n 个区间 [l_i,r_i]。再给定 q 次询问,给出 L,R,求最长的 [x,y] 使得 \forall i \in [x,y], [l_i,r_i] \cap [L,R] \ne \varnothing。输出 (y-x+1)_{\max}。

:::::success[题解]

对询问做最大子段和状物,顺序扫描每个区间并维护当前答案 v。若 [l_i,r_i] \cap [L,R] \ne \varnothing 则令 v \gets v+1,否则 v \gets 0。最终 v 的历史 \max 即为答案,复杂度 O(nq)。

转二维平面分析,将 (l_i,r_i) 视为二维平面上的点,则查询 (L,R) 是对 r_i \ge L \land l_i \le R 的点 +1,不满足的点清零,查询历史 \max。

注意到 i 的限制不好处理,考虑将询问离线并变换视角,顺序扫描每个 i 并更新其关联的所有询问。每轮扫描需要做 2-side 矩形 +1 和 2-side 矩形清零,并维护每个询问对应的历史 \max。可以用 KDT 维护,最后提取叶节点的信息即为答案。

用 (\max,+) 矩阵推一下,节点上维护向量 \begin{bmatrix}V \\ H \\0 \end{bmatrix} 表示当前值和历史 \max。加 x 和清空的矩阵分别是

\begin{aligned} \begin{bmatrix} x & -\infty & \infty \\ x & 0 & -\infty\\ -\infty & -\infty & 0 \end{bmatrix} \begin{bmatrix}V \\ H \\0 \end{bmatrix}&=\begin{bmatrix}V+x \\ \max(H,V+x) \\0 \end{bmatrix}\\ \begin{bmatrix} -\infty & -\infty & 0 \\ -\infty & 0 & -\infty\\ -\infty & -\infty & 0 \end{bmatrix}\begin{bmatrix}V \\ H \\0 \end{bmatrix}&=\begin{bmatrix}0 \\ H \\0 \end{bmatrix} \end{aligned}

复杂度 O(n \sqrt{q}),由于常数较大难以通过。

两个常数优化:维护形如 \begin{bmatrix} A & -\infty & B \\ C & 0 & D\\ -\infty & -\infty & 0 \end{bmatrix} 的标记,手动模拟矩阵乘法;不要把修改拆成四个矩形,直接写递归函数即可。

:::::

:::::info[代码]

const int N = 5e4 + 5, M = 2e5 + 5, inf = 2e9;
int n, m, l[N], r[N], ans[M];
struct node {
    int x, y, id;
} q[M];

using tag_t = tuple<i64, i64, i64, i64>;
using info_t = pair<i64, i64>;
const tag_t I = {0, -inf, -inf, -inf};
const tag_t A1 = {1, -inf, 1, -inf};
const tag_t C = {-inf, 0, -inf, -inf};
info_t operator+ (const info_t& a, const info_t& b) {
    return {max(a.fi, b.fi), max(a.se, b.se)};
}
info_t operator* (const tag_t& u, const info_t& v) {
    auto [a, b, c, d] = u; auto [x, h] = v;
    return {max(a + x, b), max({c + x, d, h})};
}
tag_t operator+ (const tag_t& a, const tag_t& b) {
    auto [a1, b1, c1, d1] = a; auto [a2, b2, c2, d2] = b;
    return {a1 + a2, max(a1 + b2, b1), max(c1 + a2, c2), max({c1 + b2, d1, d2})};
}

#define ls (rt << 1)
#define rs (rt << 1 | 1)
struct range {
    int x1, y1, x2, y2, len;
    range() : x1(inf), y1(inf), x2(-inf), y2(-inf), len(0) {}
} rect[M << 2];
int qid[M << 2];
info_t val[M << 2]; tag_t tag[M << 2];
void pushup(int rt) {val[rt] = val[ls] + val[rs];}
void apply(int rt, tag_t c) {val[rt] = c * val[rt], tag[rt] = c + tag[rt];}
void pushdown(int rt) {
    if (tag[rt] == I) return;
    apply(ls, tag[rt]), apply(rs, tag[rt]), tag[rt] = I;
}
void build(int l = 1, int r = m, int rt = 1) {
    tag[rt] = I, rect[rt].len = r - l + 1;
    for (int i = l; i <= r; i++) {
        chkmin(rect[rt].x1, q[i].x), chkmin(rect[rt].y1, q[i].y);
        chkmax(rect[rt].x2, q[i].x), chkmax(rect[rt].y2, q[i].y);
    }
    if (l == r) return qid[rt] = q[l].id, void();
    int mid = (l + r) >> 1, op = rect[rt].x2 - rect[rt].x1 > rect[rt].y2 - rect[rt].y1;
    nth_element(q + l, q + mid, q + r + 1, [&](const node& a, const node& b) -> bool {
        return op ? a.x < b.x : a.y < b.y;
    });
    build(l, mid, ls), build(mid + 1, r, rs);
}
void update(int x, int y, int rt = 1) {
    if (rect[rt].x2 <= x && rect[rt].y1 >= y) return apply(rt, A1);
    if (rect[rt].x1 > x || rect[rt].y2 < y) return apply(rt, C);
    pushdown(rt), update(x, y, ls), update(x, y, rs);
}
void solve(int rt = 1) {
    if (rect[rt].len == 1) return ans[qid[rt]] = val[rt].se, void();
    pushdown(rt), solve(ls), solve(rs);
}

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    for (int i = 1; i <= m; i++) cin >> q[i].x >> q[i].y, q[i].id = i;
    build();
    for (int i = 1; i <= n; i++) update(r[i], l[i]);
    solve();
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
} 

:::::