K-D Tree
stripe_python · · 算法·理论
模拟赛用到了,但之前写过
OI 里用的 K-D Tree 一般都是 2-D Tree,用来解决 4-side 矩形的修改查询问题。
建树
维护一个平面点集,每次选取长边按中位数切开,递归建树。
可以证明树高是
精细实现下时间
查询 / 修改
- 查询:将 4-side 矩形拆成若干块,将信息合并起来。
- 修改:将 4-side 矩形拆成若干块,对应节点上打标记。
和线段树一样,KDT 支持查询的是半群信息。单次操作复杂度
插入 / 删除
如果要在点集中插入 / 删除一些点,kdt 可能保持不了平衡,复杂度就爆了。
常用的解决方法:
- 替罪羊式重构:设置平衡度
\alpha ,当左右子树大小比例超过\alpha 则拍扁重构。注意此时树高不满足\log_2 n 的要求,复杂度不是根号。取\alpha=0.6 查询复杂度取得O(n^{0.57}) 。 - 定期重构:子树中每
B 次插入 / 删除重构一次,取B=\sqrt{n \log n} 则查询修改的复杂度均为O(\sqrt{n \log n}) 。 - 二进制分组:维护若干棵大小为
1,2,4,\cdots, 2^k 的 KDT,插入时新增一棵大小为1 的 kdt,然后将相同大小的树合并并拍扁重构。均摊以后修改O(\log^2 n) ,查询在每棵树上分别查询再合并信息,复杂度O(\sqrt{n}) 。 - 离线:如果出题人大发善心允许离线,直接将插入的点离线下来建树。
实际上 OI 中取
其他用途
- KDT 分治:把询问挂在叶节点,自顶向下处理询问。利用的是 KDT 的结构。
- KDT 优化建图:主要是 4-side 矩形连边的问题。优势在于节点数是线性的。
一般来说,不需要插入删除的静态 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[题解]
对询问做最大子段和状物,顺序扫描每个区间并维护当前答案
转二维平面分析,将
注意到
用
复杂度
两个常数优化:维护形如
:::::
:::::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';
}
:::::