几个月后的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 #include4 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 }
3种写法可选
<1>插入的时候采用替罪羊树的方法来维护，子树太偏就直接重构
<2>一开始直接把所有点扔进kdtree，用flag来标记该点是否被激活
<3>直接插入不重构。事实上本题没有出极端数据导致树会特别偏，所以可过。这种写法需要稍稍注意常数
2) bzoj 4066 二维平面，单点修改，区间查询，强制在线
1 #include2 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 }
正直写法，子树size过大就要Rebuild
判断rebuild的系数取的0.75，注意rebuild不是在回溯过程中当前子树不平衡就立刻重构
而是回溯过程中找到最靠近根的需要重构的子树根节点，然后对这棵树进行重构
详情看代码
不正直写法，新节点先存在数组里，查询时遍历该数组+查询kdtree
当数组size大于K时，把数组里的点放进kdtree并重构整颗kdtree
K取10000即可，可过
3) bzoj4154 二维平面，区间覆盖，单点查询
1 #include2 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 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 }
重点在于观察到修改的是一定距离以内的子节点
所以考虑转换到二维平面，一维为dfs序，一维为dep
通过子树区间+深度区间限制，即可得到修改的点集
二维平面上区间覆盖+单点查询，kdtree即可
4) bzoj3489 求区间内最大的只出现过一次的数
1 #include2 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 }
考虑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