kdtree

感觉kdtree是主席树的升级版,建树的过程非常的像,但是查询的过程不太一样

问题

二维平面,给定n个点。\(1\le n\le 1e6\),后面有q个查询,(sx, tx, sy, ty)查询一个平面内点的个数。

问题的升级版

若有顶点的插入和删除,该怎么操作?(突然想起晚上打的cf里面的节点的删除该怎么样高效的进行操作?

巨巨说主席树+带修, 并没有什么思路。

原理

可以看看qsc推荐的知乎的一个教程,感觉可以理解一下。
通过中间的不断的切割,并且对x,y轴进行排序,从而降低查询的复杂度

未验证的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
struct Node{
int pos;
int l, r;
Node(){};
Node(int pos, int l, int r):pos(pos), l(l), r(r){};
};
struct Point{
int id, x, y;
Point(){};
Point(int _id, int _x, int _y):id(_id), x(_x), y(_y){};
//答案要求输出的结果按照输入点的顺序来
bool operator < (const Point &p)const{
return id<p.id;
}
};
bool cmpx(Point a, Point b){return a.x<b.x;}
bool cmpy(Point a, Point b){return a.y<b.y;}
int n;
Point p[maxn];
Node node[maxn];
int rt;
int cnt = 0;
int make_kdtree(int l, int r, int depth){
if(!(l<r)) return -1;
int mid = (l+r)/2;
//cout<<"test:"<<l<<" "<<mid<<" "<<r<<endl;
//感觉kdree和主席树的区别就在这个地方
if(depth%2 == 0){
sort(p+l, p+r, cmpx);
}
else{
sort(p+l, p+r, cmpy);
}
int t = rt++;
node[t].pos = mid;
node[t].l = make_kdtree(l, mid, depth+1);
node[t].r = make_kdtree(mid+1, r, depth+1);
return t;
}
void find_node(int rt, int sx, int tx, int sy, int ty,
int depth, vector<Point> &ans){
int x = p[node[rt].pos].x;
int y = p[node[rt].pos].y;
//cout<<"test:"<<x<<" "<<y<<endl;
if(x>=sx&&x<=tx&&y<=ty&&y>=sy){
ans.push_back(p[node[rt].pos]);
}
if(depth%2 == 0){
if(node[rt].l!=-1){
if(sx<=x){
find_node(node[rt].l, sx, tx, sy, ty, depth+1, ans);
}
}
if(node[rt].r!=-1){
if(x<=tx){
find_node(node[rt].r, sx, tx, sy, ty, depth+1, ans);
}
}
}
else{
if(node[rt].l!=-1){
if(sy<=y){
find_node(node[rt].l, sx, tx,sy,ty, depth+1, ans);
}
}
if(node[rt].r!=-1){
if(y<=ty){
find_node(node[rt].r, sx, tx, sy, ty, depth+1, ans);
}
}
}
}
int main()
{
while(~scanf("%d", &n)){
for(int i=0; i<n; i++){
int x, y;
scanf("%d%d", &x, &y);
p[i].x = x, p[i].y = y, p[i].id = i;
node[i].l = node[i].r = node[i].pos = -1;
}
rt = 0;
int root = make_kdtree(0, n, 0);
int q;
scanf("%d", &q);
// for(int i=0; i<=n; i++){
// printf("%d: %d %d %d\n", i, node[i].pos, node[i].l, node[i].r);
// }
int sx, sy, tx, ty;
vector<Point> ans;
for(int i=0; i<q; i++){
scanf("%d%d%d%d", &sx, &tx, &sy, &ty);
ans.clear();
find_node(root, sx, tx, sy, ty, 0, ans);
sort(ans.begin(), ans.end());
for(vector<Point>::iterator it = ans.begin(); it!=ans.end();
it++){
printf("%d\n", it->id);
}
printf("\n");
}
}
return 0;
}
/*
6
2 1
2 2
4 2
6 2
3 3
5 4
2
2 4 0 4
4 10 2 5
*/
//output
/*
0
1
2
4
2
3
5
*/

未解决的问题

文章目录
  1. 1. 问题
    1. 1.1. 问题的升级版
    2. 1.2. 原理
    3. 1.3. 未验证的代码
  2. 2. 未解决的问题
{{ live2d() }}