K-D Tree

Posted on Edited on In Word count in article: 3.2k Reading time ≈ 12 mins.
K-D Tree 入门

\(K-D\;Tree\)

处理高维空间的数据结构

建树

每次取离散化程度最高的维度的中点作为一个节点，所以整个建树的过程与归并排序类似（这里用 \(k = 2\) 举例）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Build(int l, int r) {
    if (l > r) return 0;
    int mid((l + r) >> 1);
    double AvergX(0), AvergY(0), ValX(0), ValY(0);
    
    for (int i = l; i <= r; ++i) {
        AvergX += P[i].x;
        AvergY += P[i].y;
    }
    AvergX /= (r - l + 1.0), AvergY /= (r - l + 1.0);
    for (int i = l; i <= r; ++i) {
        ValX += pow(P[i].x - AvergX);
        ValY += pow(P[i].y - AvergY);
    }

    if (ValX > ValY) nth_element (P + l, P + mid, P + r + 1, CompareX);
    else nth_element (P + l, P + mid, P + r + 1, CompareY);

    Son[mid][0] = Build (l, mid - 1);
    Son[mid][1] = Build (mid + 1, r);

    return mid;
}

可以证明对于 \(n\) 个节点的一棵树的时间复杂度为 \(O(n\log n)\)

插入

记录插入节点的排序维度，按顺序依次插入左（右）节点，如果某个节点左右失去平衡，则考虑重构这个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool Bad(int X) { return Par * Size[X] <= (double)max(Size[LS[X]], Size[RS[X]]);}

void ReSort(int X)
{
    if (!X) return ;
    ReSort(LS[X]);
    Cnt[++T] = X;
    ReSort(RS[X]);
}

inline void ReBuilt(int &X)
{
    T = 0;
    ReSort(X);
    X = Build(1, T);
}

查询

这类问题大致询问两点之间的距离，所以可以记录一个子树包含的最大矩形，可以构造估价函数，做类似 \(A^*\) 的剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void QueryMax(int l, int r) {
    if (l > r) return ;
    int mid ((l + r) >> 1);
    MaxAns = max(MaxAns, Distante(mid));
    if (l == r) return ;

    double ExpAnsl = ExpMaxDis (Son[mid][0]);
    double ExpAnsr = ExpMaxDis (Son[mid][1]);
 
    if (ExpAnsl > ExpAnsr) {//加大剪枝力度，尽可能不让复杂度变为O(n)
        if (ExpAnsl > MaxAns && Son[mid][0]) QueryMax (l, mid - 1);
        if (ExpAnsr > MaxAns && Son[mid][1]) QueryMax (mid + 1, r);
    } else {
        if (ExpAnsr > MaxAns && Son[mid][1]) QueryMax (mid + 1, r);
        if (ExpAnsl > MaxAns && Son[mid][0]) QueryMax (l, mid - 1);
    }
}

查询的时间复杂度为 \(O(\log n)\sim O(n)\)

例题

(CQOI2016)K 远点对

题目描述

已知平面内 \(N\) 个点的坐标，求欧氏距离下的第 \(K\) 远点对。

两个点 \(P(x_1,y_1)\) 和 \(Q(x_2,y_2)\) 的欧氏距离定义为 \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)

输入格式

输入文件第一行为用空格隔开的两个整数 \(N,K\) 。

接下来 \(N\) 行，每行两个整数 \(X,Y\) ，表示一个点的坐标。

输出格式

输出文件第一行为一个整数，表示第 \(K\) 远点对的距离的平方（一定是个整数）。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1

样例输出 #1

1
9

提示

对于 \(100\%\) 的测试点，\(N \le 100000,1 \le K \le 100,K \le \dfrac {N(N-1)}{2},0 \le X,Y < 2^{31}\)

思路

对输入的点建树，然后查询所有的点，考虑到会重复计算，所以小根堆的大小要变为题设的二倍

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 1e5 + 10, Mod = 1e9 + 7;
int N, K, Son[Maxn][2];
int XMin[Maxn], XMax[Maxn], YMin[Maxn], YMax[Maxn];
priority_queue <ll, vector<ll>, greater<ll> > Q;
struct Node {int X, Y;}P[Maxn];

inline bool CmpX(Node A, Node B) {return A.X < B.X;}
inline bool CmpY(Node A, Node B) {return A.Y < B.Y;}

inline void Rectangle(int X)
{
    XMin[X] = XMax[X] = P[X].X;
    YMin[X] = YMax[X] = P[X].Y;
    if (Son[X][0])  
        XMin[X] = min(XMin[X], XMin[Son[X][0]]), XMax[X] = max(XMax[X], XMax[Son[X][0]]),
        YMin[X] = min(YMin[X], YMin[Son[X][0]]), YMax[X] = max(YMax[X], YMax[Son[X][0]]);
    if (Son[X][1])
        XMin[X] = min(XMin[X], XMin[Son[X][1]]), XMax[X] = max(XMax[X], XMax[Son[X][1]]),
        YMin[X] = min(YMin[X], YMin[Son[X][1]]), YMax[X] = max(YMax[X], YMax[Son[X][1]]);
}

int Build(int L, int R)
{
    if (L > R) return 0;
    int Mid((L + R) >> 1);
    int Avx(0), Avy(0), Vax(0), Vay(0);
    for (int i = L; i <= R; ++i) Avx += P[i].X, Avy += P[i].Y;
    Avx /= (R - L + 1), Avy /= (R - L + 1);
    for (int i = L; i <= R; ++i)  
        Vax += (P[i].X - Avx) * (P[i].X - Avx), 
        Vay += (P[i].Y - Avy) * (P[i].Y - Avy);
    if (Vax > Vay) nth_element(P + L, P + Mid, P + R + 1, CmpX);
    else nth_element(P + L, P + Mid, P + R + 1, CmpY);
    Son[Mid][0] = Build(L, Mid - 1), Son[Mid][1] = Build(Mid + 1, R);
    Rectangle(Mid);
    return Mid;
}

inline ll Pow(int X) {return 1ll * X * X;}

inline ll F(int A, int B)
{
    return max(Pow(XMin[A] - P[B].X), Pow(XMax[A] - P[B].X)) + 
           max(Pow(YMin[A] - P[B].Y), Pow(YMax[A] - P[B].Y));
}

void Query(int L, int R, int T)
{
    if (L > R) return ;
    int Mid((L + R) >> 1);
    ll Temp = Pow(P[Mid].X - P[T].X) + Pow(P[Mid].Y - P[T].Y);
    if (Temp > Q.top()) Q.pop(), Q.push(Temp);
    if (L == R) return ;
    ll DisL = F(Son[Mid][0], T), DisR = F(Son[Mid][1], T);
    if (DisL > Q.top()) Query (L, Mid - 1, T);
    if (DisR > Q.top()) Query (Mid + 1, R, T);
}

int main()
{
    scanf ("%d %d", &N, &K);
    for (int i = 1; i <= (K << 1); ++i) Q.push(0);
    for (int i = 1; i <= N; ++i) scanf ("%d %d", &P[i].X, &P[i].Y);
    Build (1, N);
    for (int i = 1; i <= N; ++i) Query (1, N, i);
    printf ("%lld\n", Q.top());
    system("pause");
}

[SDOI2012]最近最远点对

题目描述

给定平面直角坐标系上的 \(n\) 个点，分别求出距离最近的两个点的距离和距离最远的两个点的距离。注意，距离为直线距离()。

输入格式

第一行一个整数，\(n\)。 接下来 \(n\) 行每行两个非负浮点数，\(x_i\),\(y_i\)，表示第 \(i\) 个点的 X 坐标与 Y 坐标。

输出格式

总共一行，两个浮点数，为最短距离与最长距离。误差不超过 \(0.01\) 视为正确。

样例 #1

样例输入 #1

1
2
3
4
5
4
0.0 0.0
0.0 1.0
1.0 0.0
1.0 1.0

样例输出 #1

1
1.00 1.41

提示

  • 对于 \(30\%\) 的数据，\(n\leq 2000\)；
  • 对于 \(70\%\) 的数据，\(n\leq 20000\)；
  • 对于 \(100\%\) 的数据，\(0 \lt n\leq 10^5\)，输入数据中所有数均为不超过 \(10^9\) 的非负数。

也是很模板的一道题了，注意剪枝

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
140
141
142
143
144
145
//静态K——D Tree 模板
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e5 + 10;

struct Points { double x, y; }P[Maxn];

int Son[Maxn][2], target;
double MaxX[Maxn], MaxY[Maxn];
double MinX[Maxn], MinY[Maxn];

inline bool CompareX (Points A, Points B) {
    return A.x < B.x;
}

inline bool CompareY (Points A, Points B) {
    return A.y < B.y;
}

inline void Rectangle (int x) {
    MaxX[x] = MinX[x] = P[x].x;
    MaxY[x] = MinY[x] = P[x].y;

    if (Son[x][0]) {
        MaxX[x] = max (MaxX[x], MaxX[Son[x][0]]);
        MaxY[x] = max (MaxY[x], MaxY[Son[x][0]]);
        MinX[x] = min (MinX[x], MinX[Son[x][0]]);
        MinY[x] = min (MinY[x], MinY[Son[x][0]]);
    }

    if (Son[x][1]) {
        MaxX[x] = max (MaxX[x], MaxX[Son[x][1]]);
        MaxY[x] = max (MaxY[x], MaxY[Son[x][1]]);
        MinX[x] = min (MinX[x], MinX[Son[x][1]]);
        MinY[x] = min (MinY[x], MinY[Son[x][1]]);
    }
}

inline double pow(double x) {
    return x * x;
}

int Build(int l, int r) {
    if (l > r) return 0;
    int mid((l + r) >> 1);
    double AvergX(0), AvergY(0), ValX(0), ValY(0);
    
    for (int i = l; i <= r; ++i) {
        AvergX += P[i].x;
        AvergY += P[i].y;
    }
    AvergX /= (r - l + 1.0), AvergY /= (r - l + 1.0);
    for (int i = l; i <= r; ++i) {
        ValX += pow(P[i].x - AvergX);
        ValY += pow(P[i].y - AvergY);
    }

    if (ValX > ValY) nth_element (P + l, P + mid, P + r + 1, CompareX);
    else nth_element (P + l, P + mid, P + r + 1, CompareY);

    Son[mid][0] = Build (l, mid - 1);
    Son[mid][1] = Build (mid + 1, r);

    Rectangle (mid);
    return mid;
}

double MaxAns, MinAns(1e18);

inline double ExpMaxDis(int pa) {
    return max (pow (MaxX[pa] - P[target].x), pow (MinX[pa] - P[target].x)) + 
           max (pow (MaxY[pa] - P[target].y), pow (MinY[pa] - P[target].y));
}

inline double ExpMinDis(int pa) {
    double ans(0);
    if (MinX[pa] > P[target].x) ans += pow(MinX[pa] - P[target].x);
    if (MaxX[pa] < P[target].x) ans += pow(MaxX[pa] - P[target].x);
    if (MinY[pa] > P[target].y) ans += pow(MinY[pa] - P[target].y);
    if (MaxY[pa] < P[target].y) ans += pow(MaxY[pa] - P[target].y);
    return ans;
}

inline double Distante(int pa) {
    return pow(P[pa].x - P[target].x) + pow(P[pa].y - P[target].y);
}

void QueryMax(int l, int r) {
    if (l > r) return ;
    int mid ((l + r) >> 1);
    MaxAns = max(MaxAns, Distante(mid));
    if (l == r) return ;

    double ExpAnsl = ExpMaxDis (Son[mid][0]);
    double ExpAnsr = ExpMaxDis (Son[mid][1]);
 
    if (ExpAnsl > ExpAnsr) {
        if (ExpAnsl > MaxAns && Son[mid][0]) QueryMax (l, mid - 1);
        if (ExpAnsr > MaxAns && Son[mid][1]) QueryMax (mid + 1, r);
    } else {
        if (ExpAnsr > MaxAns && Son[mid][1]) QueryMax (mid + 1, r);
        if (ExpAnsl > MaxAns && Son[mid][0]) QueryMax (l, mid - 1);
    }
}

void QueryMin(int l, int r) {
    if (l > r) return ;
    int mid ((l + r) >> 1);
    if (mid != target) MinAns = min(MinAns, Distante(mid));
    if (l == r) return ;

    double ExpAnsl = ExpMinDis (Son[mid][0]);
    double ExpAnsr = ExpMinDis (Son[mid][1]);

    if (ExpAnsl < ExpAnsr) {
        if (ExpAnsl < MinAns && Son[mid][0]) QueryMin (l, mid - 1);
        if (ExpAnsr < MinAns && Son[mid][1]) QueryMin (mid + 1, r);
    } else {
        if (ExpAnsr < MinAns && Son[mid][1]) QueryMin (mid + 1, r);
        if (ExpAnsl < MinAns && Son[mid][1]) QueryMin (l, mid - 1);
    }
}

int main() {
    int n;

    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf ("%lf %lf", &P[i].x, &P[i].y);
        

    Build (1, n);

    int maxn = (n + 1) >> 1;
    for (target = 1; target <= maxn; ++target) {
        QueryMax (1, n);
        QueryMin (1, n);
    }

    printf ("%lf %lf\n", sqrt(MinAns), sqrt(MaxAns));
    system ("pause");
    return 0;
}

(SDOI2010)捉迷藏

题目描述

iPig在大肥猪学校刚上完了无聊的猪文课，天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞，为了消除寂寞感，他决定和他的好朋友giPi（鸡皮）玩一个更加寂寞的游戏——捉迷藏。

但是，他们觉得，玩普通的捉迷藏没什么意思，还是不够寂寞，于是，他们决定玩寂寞无比的螃蟹版捉迷藏，顾名思义，就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后，他们决定iPig去捉giPi。由于他们都很熟悉大肥猪学校的地形了，所以giPi只会躲在大肥猪学校内N个隐秘地点，显然iPig也只会在那N个地点内找giPi。游戏一开始，他们从这N个隐秘地点之中选定一个地点，iPig保持不动，然后giPi用30秒的时间逃离现场（显然，giPi不会呆在原地）。然后iPig会随机地去找giPi，直到找到为止。由于iPig很懒，所以他到总是走最短的路径，而且，他选择起始点不是随便选的，他想找一个地点，使得该地点到（除了这个地点以外的）最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。

由于iPig现在手上没有电脑，所以不能编程解决这个如此简单的问题，所以他马上打了个电话，要求你帮他解决这个问题。iPig告诉了你大肥猪学校的N个隐秘地点的坐标，请你编程求出iPig的问题。

输入格式

输入文件hideseek.in：

第1行：一个整数N；

第2 ~ (N + 1)行：每行两个整数Xi，Yi，表示第i个地点的坐标。

输出格式

输出文件hideseek.out有且仅有一行：一个整数，为距离差的最小值。

样例 #1

样例输入 #1

1
2
3
4
5
4
0 0
1 0
0 1
1 1

样例输出 #1

1
1

提示

30%的数据中，2 <= N <= 1000；

100%的数据中，2 <= N <= 100000，0 <= Xi, Yi <= 100000000。

数据保证没有重点。

通过这道题可以发现，除了欧几里得距离，\(K-D\;Tree\) 还可以处理曼哈顿距离

注意估价函数的正确性，否则可能 \(\text{RE}，\text{WA}\)

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10, inf = 0x7fffffff;
int target, son[maxn][2];
int minx[maxn], maxx[maxn], miny[maxn], maxy[maxn];
pair <int, int> p[maxn];

inline int read() {
    int t(0);
    char c(getchar());
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) {
        t = (t << 1) + (t << 3) + (c ^ 48);
        c = getchar();
    }
    return t;
}

inline void Rectangle (int x) {
    maxx[x] = minx[x] = p[x].first;
    maxy[x] = miny[x] = p[x].second;
    for (int i = 0; i < 2; ++i) 
        if (son[x][i]) {
            maxx[x] = max (maxx[x], maxx[son[x][i]]), maxy[x] = max (maxy[x], maxy[son[x][i]]),
            minx[x] = min (minx[x], minx[son[x][i]]), miny[x] = min (miny[x], miny[son[x][i]]);
        }
}

int Build (int l, int r) {
    if (l > r) return 0;
    int mid((l + r) >> 1);
    ll Avex(0), Avey(0), Valx(0), Valy(0);

    for (int i = l; i <= r; ++i)
        Avex += p[i].first,
        Avey += p[i].second;
    Avex /= (r - l + 1), Avey /= (r - l + 1);
    for (int i = l; i <= r; ++i)
        Valx += pow (Avex - p[i].first, 2),
        Valy += pow (Avey - p[i].second, 2);

    if (Valx > Valy) nth_element (p + l, p + mid, p + r + 1, [] (pair <int, int> A, pair <int, int> B) 
                                                                            {return A.first < B.first;});
    else nth_element (p + l, p + mid, p + r + 1, [](pair <int, int> A, pair <int, int> B) 
                                                                            {return A.second < B.second;});
    
    son[mid][0] = Build(l, mid - 1);
    son[mid][1] = Build (mid + 1, r);

    Rectangle (mid);
    return mid;
}

inline int ExpMaxDis(int now) {
    return max (abs(maxx[now] - p[target].first), abs(minx[now] - p[target].first)) +
           max (abs(maxy[now] - p[target].second), abs(miny[now] - p[target].second));
}

inline int ExpMinDis(int now) {
    int ans(0), x(p[target].first), y(p[target].second);
    if (x < minx[now]) ans += minx[now] - x;
    if (x > maxx[now]) ans += x - maxx[now];
    if (y < miny[now]) ans += miny[now] - y;
    if (y > maxy[now]) ans += y - maxy[now];
    return ans;
}

inline int Distance(int now) {
    return abs (p[now].first - p[target].first) + 
           abs (p[now].second - p[target].second);
}

int Minans, Maxans, Ans(inf);

void QueryMax(int l, int r) {
    if (l > r) return ;
    int mid ((l + r) >> 1);
    if (mid ^ target) Maxans = max(Maxans, Distance (mid));
    if (l == r) return ;

    int ansl = ExpMaxDis (son[mid][0]), ansr = ExpMaxDis (son[mid][1]);
    if (ansl > ansr) {
        if (ansl > Maxans && son[mid][0]) QueryMax (l, mid - 1);
        if (ansr > Maxans && son[mid][1]) QueryMax (mid + 1, r);
    } else {
        if (ansr > Maxans && son[mid][1]) QueryMax (mid + 1, r);
        if (ansl > Maxans && son[mid][0]) QueryMax (l, mid - 1);
    }
}

void QueryMin(int l, int r) {
    if (l > r) return ;
    int mid ((l + r) >> 1);
    if (mid ^ target) Minans = min(Minans, Distance (mid));
    if (l == r) return;

    int ansl = ExpMinDis (son[mid][0]), ansr = ExpMinDis (son[mid][1]);
    if (ansl < ansr) {
        if (ansl < Minans && son[mid][0]) QueryMin (l, mid - 1);
        if (ansr < Minans && son[mid][1]) QueryMin (mid + 1, r); 
    } else {
        if (ansr < Minans && son[mid][1]) QueryMin (mid + 1, r);
        if (ansl < Minans && son[mid][0]) QueryMin (l, mid - 1);
    }
}

int main() {
    int n(read());
    for (int i = 1; i <= n; ++i) 
        p[i].first = read(), p[i].second = read();
    
    Build (1, n);

    for (target = 1; target <= n; ++target) {
        Maxans = 0, Minans = inf;
        QueryMax(1, n), QueryMin(1, n);
        Ans = min(Ans, Maxans - Minans);
    }

    cout << Ans << endl;
    system ("pause");
    return 0;
}