当前位置： ag凯发k8国际 > 编程资源 > 编程问答 >内容正文

编程问答

kd树学习小结 -ag凯发k8国际

发布时间：2023/12/20 编程问答 18 豆豆

ag凯发k8国际收集整理的这篇文章主要介绍了 kd树学习小结小编觉得挺不错的,现在分享给大家,帮大家做个参考.

几个月后的upd:

学习完下面之后，实战中的总结:

0.比赛中正解就是kdtree的题目很少很少

1.几类优先考虑kdtree的题目：

　　k(维度) >= 3 的题目

　　二维平面上涉及区间标记的题目

2. 二维平面上的题目， n >= 5w 谨慎使用kdtree

非强制在线考虑cdq套数据结构(不涉及标记的话基本考虑树状数组)

强制在线考虑树状数组套主席树(该方法需要提前确定空间够不够o(nlogn2))

　 几种方法的常数比较:cdq套树 < 树套树 < kdtree

　编程复杂度也是cdq最小，后面两个差不多

3.非写kdtree不可的题目，常数上的几个优化

　<0>快速读入，快速输出的话，不超过50w的个数基本没必要

　<1>重构kdtree的参数选择，插入多查询少的情况，最优参数是接近 0.5 x / (x y) 的

　　 x是插入个数，y是查询个数

插入少查询多的话，最优参数其实是更接近 0.7 x / (x y) 的，查询再多也不建议参数低于0.7

　　 当然最优参数的话，有时间可以自己去测试调整

　<2>其实update函数那里吧两个 if 直接写成 max / min 未必时间会差一点，可以自己尝试测试时间

学习资料在这里

对于k维kdtree，实际时间复杂度为o(n*n^(1-1/k))

build实现类似spaly，不断选一维从中间划分，可以循环选取维度，也可以rand % k

求最近点的query，重点在于其中的估价函数

求区间和的query，则和线段树类似

例题：

1) bzoj 2648求最近点

1 /*为了维持树的平衡，可以一开始把所有点都读进来build 2 然后打flag标记该点是否被激活*/ 3 #include 4 5 using namespace std; 6 7 const int n = 5e5 5; 8 9 const int inf = 1 << 30; 10 11 int n, m; 12 13 int ql, qr, ans, tot, nowd; 14 //nowd = rand() & 1 ? 15 struct node { 16 int d[2]; 17 18 bool operator < (const node &a) const { 19 if (d[nowd] == a.d[nowd]) return d[!nowd] < a.d[!nowd]; 20 return d[nowd] < a.d[nowd]; 21 } 22 }pot[n]; 23 24 struct node { 25 int min[2], max[2], d[2]; 26 node *c[2]; 27 28 node() { 29 min[0] = min[1] = max[0] = max[1] = d[0] = d[1] = 0; 30 c[0] = c[1] = null; 31 } 32 33 node(int x, int y); 34 35 void update(); 36 37 38 }t[n], null, *root; 39 40 node::node(int x, int y) { 41 min[0] = max[0] = d[0] = x; 42 min[1] = max[1] = d[1] = y; 43 c[0] = c[1] = &null; 44 } 45 46 inline void node::update() { 47 if (c[0] != &null) { 48 if (c[0] -> max[0] > max[0]) max[0] = c[0] -> max[0]; 49 if (c[0] -> max[1] > max[1]) max[1] = c[0] -> max[1]; 50 if (c[0] -> min[0] < min[0]) min[0] = c[0] -> min[0]; 51 if (c[0] -> min[1] < min[1]) min[1] = c[0] -> min[1]; 52 } 53 if (c[1] != &null) { 54 if (c[1] -> max[0] > max[0]) max[0] = c[1] -> max[0]; 55 if (c[1] -> max[1] > max[1]) max[1] = c[1] -> max[1]; 56 if (c[1] -> min[0] < min[0]) min[0] = c[1] -> min[0]; 57 if (c[1] -> min[1] < min[1]) min[1] = c[1] -> min[1]; 58 } 59 } 60 61 inline void build(node *&o, int l, int r, int d) { 62 int mid = l r >> 1; 63 nowd = d; 64 nth_element(pot l, pot mid, pot r 1); 65 o = new node(pot[mid].d[0], pot[mid].d[1]); 66 67 if (l != mid) build(o -> c[0], l, mid - 1, !d); 68 if (r != mid) build(o -> c[1], mid 1, r, !d); 69 o -> update(); 70 } 71 72 inline void insert(node *o) { 73 node *p = root; 74 int d = 0; 75 while (1) { 76 if (o -> max[0] > p -> max[0]) p -> max[0] = o -> max[0]; 77 if (o -> max[1] > p -> max[1]) p -> max[1] = o -> max[1]; 78 if (o -> min[0] < p -> min[0]) p -> min[0] = o -> min[0]; 79 if (o -> min[1] < p -> min[1]) p -> min[1] = o -> min[1]; 80 81 if (o -> d[d] >= p -> d[d]) { 82 if (p -> c[1] == &null) { 83 p -> c[1] = o; 84 return; 85 } else p = p -> c[1]; 86 } else { 87 if (p -> c[0] == &null) { 88 p -> c[0] = o; 89 return; 90 } else p = p -> c[0]; 91 } 92 d ^= 1; 93 } 94 } 95 96 inline int dist(node *o) { 97 int dis = 0; 98 if (ql < o -> min[0]) dis = o -> min[0] - ql; 99 if (ql > o -> max[0]) dis = ql - o -> max[0]; 100 if (qr < o -> min[1]) dis = o -> min[1] - qr; 101 if (qr > o -> max[1]) dis = qr - o -> max[1]; 102 return dis; 103 } 104 105 inline void query(node *o) { 106 int dl, dr, d0; 107 d0 = abs(o -> d[0] - ql) abs(o -> d[1] - qr); 108 if (d0 < ans) ans = d0; 109 if (o -> c[0] != &null) dl = dist(o -> c[0]); 110 else dl = inf; 111 if (o -> c[1] != &null) dr = dist(o -> c[1]); 112 else dr = inf; 113 114 if (dl < dr) { 115 if (dl < ans) query(o -> c[0]); 116 if (dr < ans) query(o -> c[1]); 117 } else { 118 if (dr < ans) query(o -> c[1]); 119 if (dl < ans) query(o -> c[0]); 120 } 121 } 122 123 int main() { 124 ios::sync_with_stdio(false); 125 cin >> n >> m; 126 for (int i = 1; i <= n; i ) 127 cin >> pot[i].d[0] >> pot[i].d[1]; 128 build(root, 1, n, 0); 129 130 for (int x, y, z; m --; ) { 131 cin >> x >> y >> z; 132 if (x == 1) { 133 t[tot].max[0] = t[tot].min[0] = t[tot].d[0] = y; 134 t[tot].max[1] = t[tot].min[1] = t[tot].d[1] = z; 135 t[tot].c[0] = t[tot].c[1] = &null; 136 insert(&t[tot ]); 137 } else { 138 ans = inf, ql = y, qr = z; 139 query(root), printf("%d\n", ans); 140 } 141 } 142 return 0; 143 } view code

3种写法可选

<1>插入的时候采用替罪羊树的方法来维护，子树太偏就直接重构

<2>一开始直接把所有点扔进kdtree，用flag来标记该点是否被激活

<3>直接插入不重构。事实上本题没有出极端数据导致树会特别偏，所以可过。这种写法需要稍稍注意常数

2) bzoj 4066 二维平面，单点修改，区间查询，强制在线

1 #include 2 3 using namespace std; 4 5 const int inf = 1e9; 6 7 int n, m, tot, nowd; 8 9 struct node { 10 int max[2], min[2], d[2]; 11 int sum, siz, val; 12 node *c[2]; 13 14 node() { 15 max[0] = max[1] = -inf; 16 min[0] = min[1] = inf; 17 sum = val = siz = 0; 18 c[0] = c[1] = null; 19 d[0] = d[1] = 0; 20 } 21 22 void update(); 23 }null, nodes[200010], *temp[200010]; 24 25 node *root = &null; 26 27 inline void node::update() { 28 siz = c[0] -> siz c[1] -> siz 1; 29 sum = c[0] -> sum c[1] -> sum val; 30 if (c[0] != &null) { 31 if (c[0] -> max[0] > max[0]) max[0] = c[0] -> max[0]; 32 if (c[0] -> max[1] > max[1]) max[1] = c[0] -> max[1]; 33 if (c[0] -> min[0] < min[0]) min[0] = c[0] -> min[0]; 34 if (c[0] -> min[1] < min[1]) min[1] = c[0] -> min[1]; 35 } 36 if (c[1] != &null) { 37 if (c[1] -> max[0] > max[0]) max[0] = c[1] -> max[0]; 38 if (c[1] -> max[1] > max[1]) max[1] = c[1] -> max[1]; 39 if (c[1] -> min[0] < min[0]) min[0] = c[1] -> min[0]; 40 if (c[1] -> min[1] < min[1]) min[1] = c[1] -> min[1]; 41 } 42 } 43 44 inline bool cmp(const node *a, const node *b) { 45 return a -> d[nowd] < b -> d[nowd]; 46 } 47 48 inline void traverse(node *o) { 49 if (o == &null) return; 50 temp[ tot] = o; 51 traverse(o -> c[0]); 52 traverse(o -> c[1]); 53 } 54 55 inline node *build(int l, int r, int d) { 56 int mid = l r >> 1; nowd = d; 57 nth_element(temp l, temp mid, temp r 1, cmp); 58 node *res = temp[mid]; 59 res -> max[0] = res -> min[0] = res -> d[0]; 60 res -> max[1] = res -> min[1] = res -> d[1]; 61 if (l != mid) res -> c[0] = build(l, mid - 1, !d); 62 else res -> c[0] = &null; 63 if (r != mid) res -> c[1] = build(mid 1, r, !d); 64 else res -> c[1] = &null; 65 res -> update(); 66 return res; 67 } 68 69 int x, y, a, b, tmpd; 70 71 node **tmp; 72 73 inline void rebuild(node *&o, int d) { 74 tot = 0; 75 traverse(o); 76 o = build(1, tot, d); 77 } 78 79 inline void insert(node *&o, node *p, int d) { 80 if (o == &null) {o = p; return;} 81 if (p -> max[0] > o -> max[0]) o -> max[0] = p -> max[0]; 82 if (p -> max[1] > o -> max[1]) o -> max[1] = p -> max[1]; 83 if (p -> min[0] < o -> min[0]) o -> min[0] = p -> min[0]; 84 if (p -> min[1] < o -> min[1]) o -> min[1] = p -> min[1]; 85 o -> siz , o -> sum = p -> sum; 86 insert(o -> c[p -> d[d] >= o -> d[d]], p, !d); 87 if (max(o -> c[0] -> siz, o -> c[1] -> siz) > int(o -> siz * 0.75 0.5)) tmpd = d, tmp = &o; 88 } 89 90 inline int query(node *o, int d) { 91 if (o == &null) return 0; 92 if (x > o -> max[0] || y > o -> max[1] || a < o -> min[0] || b < o -> min[1]) return 0; 93 if (x <= o -> min[0] && y <= o -> min[1] && a >= o -> max[0] && b >= o -> max[1]) return o -> sum; 94 return (x <= o -> d[0] && y <= o -> d[1] && a >= o -> d[0] && b >= o -> d[1] ? o -> val : 0) 95 query(o -> c[1], !d) query(o -> c[0], !d); 96 } 97 98 int main() { 99 ios::sync_with_stdio(false); 100 cin >> m; 101 node *ttt = &null; 102 for (int t, ans = 0; ; ) { 103 cin >> t; 104 if (t == 3) break; 105 if (t == 1) { 106 cin >> x >> y >> a; 107 x ^= ans, y ^= ans, n ; 108 nodes[n].sum = nodes[n].val = a ^ ans, nodes[n].siz = 1; 109 nodes[n].max[0] = nodes[n].min[0] = nodes[n].d[0] = x; 110 nodes[n].max[1] = nodes[n].min[1] = nodes[n].d[1] = y; 111 nodes[n].c[0] = nodes[n].c[1] = &null; 112 tmp = &(ttt), insert(root, &nodes[n], 0); 113 if (*tmp != &null) rebuild(*tmp, tmpd); 114 } else { 115 cin >> x >> y >> a >> b; 116 x ^= ans, y ^= ans, a ^= ans, b ^= ans; 117 if (x > a) swap(x, a); 118 if (y > b) swap(y, b); 119 ans = query(root, 0); 120 printf("%d\n", ans); 121 } 122 } 123 return 0; 124 } view code

正直写法，子树size过大就要rebuild

判断rebuild的系数取的0.75，注意rebuild不是在回溯过程中当前子树不平衡就立刻重构

而是回溯过程中找到最靠近根的需要重构的子树根节点，然后对这棵树进行重构

详情看代码

不正直写法，新节点先存在数组里，查询时遍历该数组查询kdtree

当数组size大于k时，把数组里的点放进kdtree并重构整颗kdtree

k取10000即可，可过

3) bzoj4154 二维平面，区间覆盖，单点查询

1 #include 2 3 using namespace std; 4 5 const int n = 1e5 5; 6 7 const int mod = 1e9 7; 8 9 int nowd, x[2], y[2], z; 10 11 struct node { 12 int max[2], min[2], d[2]; 13 int val, lazy; 14 node *c[2]; 15 16 node() { 17 c[0] = c[1] = null; 18 } 19 20 void pushup(); 21 22 void pushdown(); 23 24 bool operator < (const node &a) const { 25 return d[nowd] < a.d[nowd]; 26 } 27 }null, nodes[n]; 28 29 node *root = &null; 30 31 inline void node::pushup() { 32 if (c[0] != &null) { 33 if (c[0] -> max[0] > max[0]) max[0] = c[0] -> max[0]; 34 if (c[0] -> max[1] > max[1]) max[1] = c[0] -> max[1]; 35 if (c[0] -> min[0] < min[0]) min[0] = c[0] -> min[0]; 36 if (c[0] -> min[1] < min[1]) min[1] = c[0] -> min[1]; 37 } 38 if (c[1] != &null) { 39 if (c[1] -> max[0] > max[0]) max[0] = c[1] -> max[0]; 40 if (c[1] -> max[1] > max[1]) max[1] = c[1] -> max[1]; 41 if (c[1] -> min[0] < min[0]) min[0] = c[1] -> min[0]; 42 if (c[1] -> min[1] < min[1]) min[1] = c[1] -> min[1]; 43 } 44 } 45 46 inline void node::pushdown() { 47 if (c[0] != &null) c[0] -> val = c[0] -> lazy = lazy; 48 if (c[1] != &null) c[1] -> val = c[1] -> lazy = lazy; 49 lazy = -1; 50 } 51 52 inline node *build(int l, int r, int d) { 53 int mid = l r >> 1; nowd = d; 54 nth_element(nodes l, nodes mid, nodes r 1); 55 node *res = &nodes[mid]; 56 if (l != mid) res -> c[0] = build(l, mid - 1, !d); 57 else res -> c[0] = &null; 58 if (r != mid) res -> c[1] = build(mid 1, r, !d); 59 else res -> c[1] = &null; 60 res -> pushup(); 61 return res; 62 } 63 64 inline int query(node *o) { 65 if (o == &null) return -1; 66 if (o -> lazy != -1) o -> pushdown(); 67 if (x[0] > o -> max[0] || y[0] > o -> max[1] || x[0] < o -> min[0] || y[0] < o -> min[1]) return -1; 68 if (x[0] == o -> d[0]) return o -> val; 69 return max(query(o -> c[0]), query(o -> c[1])); 70 } 71 72 inline void modify(node *o) { 73 if (o == &null) return; 74 if (o -> lazy != -1) o -> pushdown(); 75 if (x[0] > o -> max[0] || y[0] > o -> max[1] || x[1] < o -> min[0] || y[1] < o -> min[1]) return; 76 if (x[0] <= o -> min[0] && y[0] <= o -> min[1] && x[1] >= o -> max[0] && y[1] >= o -> max[1]) { 77 o -> val = o -> lazy = z; 78 return; 79 } 80 if (x[0] <= o -> d[0] && y[0] <= o -> d[1] && x[1] >= o -> d[0] && y[1] >= o -> d[1]) o -> val = z; 81 modify(o -> c[0]), modify(o -> c[1]); 82 } 83 84 int n, m, k, a[n], c[n], d[n]; 85 86 int cnt, st[n], en[n], dfn[n], dep[n]; 87 88 vector <int> e[n]; 89 90 void dfs(int u) { 91 st[u] = cnt, dfn[cnt] = u; 92 for (int v : e[u]) 93 dep[v] = dep[u] 1, dfs(v); 94 en[u] = cnt; 95 } 96 97 int main() { 98 ios::sync_with_stdio(false); 99 int t, ans; 100 for (cin >> t; t --; ) { 101 cin >> n >> m >> k, ans = cnt = 0; 102 for (int i = 1; i <= n; i ) 103 e[i].clear(); 104 for (int u, i = 2; i <= n; i ) { 105 cin >> u; 106 e[u].push_back(i); 107 } 108 dfs(1); 109 for (int i = 1; i <= n; i ) { 110 nodes[i].min[0] = nodes[i].max[0] = nodes[i].d[0] = i; 111 nodes[i].min[1] = nodes[i].max[1] = nodes[i].d[1] = dep[dfn[i]]; 112 nodes[i].val = 1, nodes[i].lazy = -1; 113 } 114 root = build(1, n, 0); 115 for (int u, v, w, i = 1; i <= k; i ) { 116 cin >> u >> v >> w; 117 if (w == 0) { 118 x[0] = st[u], y[0] = dep[u]; 119 ans = (ans 1ll * i * query(root) % mod) % mod; 120 } else { 121 x[0] = st[u], x[1] = en[u]; 122 y[0] = dep[u], y[1] = dep[u] v; 123 z = w, modify(root); 124 } 125 } 126 cout << ans << endl; 127 } 128 return 0; 129 } view code

重点在于观察到修改的是一定距离以内的子节点

所以考虑转换到二维平面，一维为dfs序，一维为dep

通过子树区间深度区间限制，即可得到修改的点集

二维平面上区间覆盖单点查询，kdtree即可

4) bzoj3489 求区间内最大的只出现过一次的数

1 #include 2 3 using namespace std; 4 5 const int n = 1e5 5; 6 7 const int mod = 1e9 7; 8 9 int nowd, ans, x[3], y[3]; 10 11 int n, m, a[n], b[n], c[n], d[n]; 12 13 struct node { 14 int max[3], min[3], d[3]; 15 int val, maxv; 16 node *c[2]; 17 18 node() { 19 c[0] = c[1] = null; 20 val = maxv = 0; 21 } 22 23 void pushup(); 24 25 bool operator < (const node &a) const { 26 return d[nowd] < a.d[nowd]; 27 } 28 }null, nodes[n]; 29 30 node *root = &null; 31 32 inline void node::pushup() { 33 if (c[0] != &null) { 34 if (c[0] -> max[1] > max[1]) max[1] = c[0] -> max[1]; 35 if (c[0] -> max[2] > max[2]) max[2] = c[0] -> max[2]; 36 if (c[0] -> min[0] < min[0]) min[0] = c[0] -> min[0]; 37 if (c[0] -> min[2] < min[2]) min[2] = c[0] -> min[2]; 38 if (c[0] -> maxv > maxv) maxv = c[0] -> maxv; 39 } 40 if (c[1] != &null) { 41 if (c[1] -> max[1] > max[1]) max[1] = c[1] -> max[1]; 42 if (c[1] -> max[2] > max[2]) max[2] = c[1] -> max[2]; 43 if (c[1] -> min[0] < min[0]) min[0] = c[1] -> min[0]; 44 if (c[1] -> min[2] < min[2]) min[2] = c[1] -> min[2]; 45 if (c[1] -> maxv > maxv) maxv = c[1] -> maxv; 46 } 47 } 48 49 inline node *build(int l, int r) { 50 int mid = l r >> 1; nowd = rand() % 3; 51 nth_element(nodes l, nodes mid, nodes r 1); 52 node *res = &nodes[mid]; 53 if (l != mid) res -> c[0] = build(l, mid - 1); 54 else res -> c[0] = &null; 55 if (r != mid) res -> c[1] = build(mid 1, r); 56 else res -> c[1] = &null; 57 res -> pushup(); 58 return res; 59 } 60 61 inline int calc(node *o) { 62 if (y[0] < o -> min[0] || x[1] > o -> max[1] || x[2] > o -> max[2] || y[2] < o -> min[2]) return -1; 63 return o -> maxv; 64 } 65 66 inline void query(node *o) { 67 if (o -> val > ans && y[0] >= o -> d[0] && x[1] <= o -> d[1] && x[2] <= o -> d[2] && y[2] >= o -> d[2]) ans = o -> val; 68 int dl, dr; 69 if (o -> c[0] != &null) dl = calc(o -> c[0]); 70 else dl = -1; 71 if (o -> c[1] != &null) dr = calc(o -> c[1]); 72 else dr = -1; 73 if (dl > dr) { 74 if (dl > ans) query(o -> c[0]); 75 if (dr > ans) query(o -> c[1]); 76 } else { 77 if (dr > ans) query(o -> c[1]); 78 if (dl > ans) query(o -> c[0]); 79 } 80 81 } 82 83 int main() { 84 ios::sync_with_stdio(false); 85 cin >> n >> m; 86 for (int i = 1; i <= n; i ) { 87 cin >> a[i]; 88 b[i] = d[a[i]]; 89 d[a[i]] = i; 90 } 91 for (int i = 1; i <= n; i ) d[i] = n 1; 92 for (int i = n; i; i --) { 93 c[i] = d[a[i]]; 94 d[a[i]] = i; 95 } 96 for (int i = 1; i <= n; i ) { 97 nodes[i].min[0] = nodes[i].d[0] = b[i]; 98 nodes[i].max[1] = nodes[i].d[1] = c[i]; 99 nodes[i].max[2] = nodes[i].min[2] = nodes[i].d[2] = i; 100 nodes[i].val = nodes[i].maxv = a[i]; 101 } 102 root = build(1, n); 103 for (int l, r; m --; ) { 104 cin >> l >> r; 105 l = (l ans) % n 1; 106 r = (r ans) % n 1; 107 if (l > r) swap(l, r); 108 y[0] = l - 1; 109 x[1] = r 1; 110 x[2] = l, y[2] = r; 111 ans = 0, query(root); 112 cout << ans << endl; 113 } 114 cout << endl; 115 return 0; 116 } view code

考虑a[i]上一次出现，和下一次出现位置分别pre[i], suc[i]

即变成pre[i], i, suc[i]在[0, l - 1], [l, r], [r 1, n 1]之间的数的最大值

3维kdtree即可，注意也要使用ans与区间最值的关系来优化

注意到3维有不需要的变量，不需要维护，40s时限跑了39s ...

简单总结:

1) 解决求最值的问题，kdtree其实就是优化暴力，所以一般都需要估价函数优化才可以

2) 非最值问题，其实感觉更像线段树，但由于奇妙的原因，所以一次更新覆盖到的区间可能达到o(sqrt(n))个

3) 由于本质是暴力，所以常数比较重要，inline，子树非空才更新，估价函数，无用信息不更新...各种优化,一般而言10w已经是极限

4) 板子题不说, kdtree的题目需要从题中找到k维平面,然后区间修改和区间查询就完事了

5) 非强制在线题目,并不优先考虑kdtree,可以考虑树套树,kdtree不强制在线可以考虑排序降维

其他例题

5) bzoj4520 给n个点,求第k远点对

solution:可以看到k比较小,所以所有点建好kdtree,对每个点查询一下,维护出一个大小为k的堆

把n个点的堆进行合并,和并出大小为2k的堆,即得到答案

6) hdu 5992

可以考虑裸的3维kdtree,能过

考虑到n比较大,不强制在线,可以按价格排序,带插入的kdtree,需要重构

这个题我打训练赛写后一种排序重构写法t到自闭

然后把那个重构的参数调整成了0.95就过了...

后来仔细考虑了一下，这个题的特点在于n很大，m不大

20w个插入，只有2w个查询

如果正常的把参数设为0.75的话，实际效率是接近o(n^(3/2))的

但参数设的比较偏的话，会减少重构次数，查询的复杂度会增加

但实际总复杂度更接近o(m*n(1/2))，所以就能a了

所以通过这个题，我们推荐重构参数设为 m/(n m) 0.5

转载于:https://www.cnblogs.com/ytytzzz/p/9625618.html

总结

以上是ag凯发k8国际为你收集整理的kd树学习小结的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。