當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

KD树学习小结

發布時間：2023/12/20 编程问答 64 豆豆

生活随笔收集整理的這篇文章主要介紹了 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 <bits/stdc++.h> 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 <bits/stdc++.h> 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 <bits/stdc++.h> 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 <bits/stdc++.h> 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

總結

以上是生活随笔為你收集整理的KD树学习小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

小结
kd