RenaMoe's Blog

念念不忘，必有回响

0%

板子 K-D Tree

发表于 更新于 分类于 ， Valine：

用于处理高维空间组织点

大概就是在某个维度下从坐标中位数二分，最后形成一棵二叉树

插入删除会导致树不平衡，需要类似替罪羊树的拍扁重建

这里先放个 2-D 的吧，针对模板题P4169

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
const int N = 6e5 + 9;
const double Alph = 0.75;// 平衡因子
const int INF = 0x7fffffff;

// 二维下的坐标及树节点
struct Pos {
    int x[2];
};
struct Node {
    int minx[2], maxx[2], ls, rs, sz;// minx，maxx存坐标范围
    Pos p;
};

int n, m, ans, root, cnt, nd;// nd为此时维度
Pos a[N];
Node tr[N];
queue<int> trash;// 垃圾回收

// 按照某个维度排序用cmp
bool operator <(Pos A, Pos B) {
    return A.x[nd] < B.x[nd];
}

// 新建节点
inline int new_node() {
    int x;
    if (trash.empty())
        x = ++cnt;
    else
        x = trash.front(), trash.pop();
    return x;
}

// 更新信息
inline void push_up(int x) {
    int ls = tr[x].ls, rs = tr[x].rs;
    // 范围
    for (int i = 0; i <= 1; ++i) {
        tr[x].minx[i] = tr[x].maxx[i] = tr[x].p.x[i];
        if (ls)
            tr[x].minx[i] = min(tr[x].minx[i], tr[ls].minx[i]), tr[x].maxx[i] = max(tr[x].maxx[i], tr[ls].maxx[i]);
        if (rs)
            tr[x].minx[i] = min(tr[x].minx[i], tr[rs].minx[i]), tr[x].maxx[i] = max(tr[x].maxx[i], tr[rs].maxx[i]);
    }
    tr[x].sz = tr[ls].sz + tr[rs].sz + 1;
}

// 建树（包括重建）
int build(int l, int r, int d) {
    if (l > r)
        return 0;
    int x = new_node(), mid = (l + r) >> 1;
    nd = d, nth_element(a+l, a+mid, a+r+1), tr[x].p = a[mid];// 找中位数
    tr[x].ls = build(l, mid-1, d^1), tr[x].rs = build(mid+1, r, d^1);
    push_up(x);
    return x;
}

// 拍扁
void pia(int x, int num) {
    if (tr[x].ls)
        pia(tr[x].ls, num);
    a[num+tr[tr[x].ls].sz+1] = tr[x].p, trash.push(x);// 把点放入a数组便于建树
    if (tr[x].rs)
        pia(tr[x].rs, num + tr[tr[x].ls].sz + 1);
}

// 检查平衡
inline void check(int &x, int d) {
    if (Alph * tr[x].sz < tr[tr[x].ls].sz || Alph * tr[x].sz < tr[tr[x].rs].sz)
        pia(x, 0), x = build(1, tr[x].sz, d);
}

// 插入点
void insert(Pos tp, int &x, int d) {
    if (!x) {
        x = new_node(), tr[x].p = tp, tr[x].ls = tr[x].rs = 0, push_up(x);
        return;
    }
    if (tp.x[d] <= tr[x].p.x[d])
        insert(tp, tr[x].ls, d^1);
    else 
        insert(tp, tr[x].rs, d^1);
    push_up(x), check(x, d);
}

顺便放一下 K-D Tree 在该题的运用

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
// 求曼哈顿距离
inline int dist(Pos A, Pos B) {
    return abs(A.x[0] - B.x[0]) + abs(A.x[1] - B.x[1]);
}

// 求点到矩形（K-D Tree上一个子树）的曼哈顿距离
inline int getdis(Pos tp, int x) {
    int sum = 0;
    for (int i = 0; i <= 1; ++i)
        sum += max(0, tp.x[i] - tr[x].maxx[i]) + max(0, tr[x].minx[i] - tp.x[i]);// 不理解就手玩一下
    return sum;
}

void query(Pos tp, int x) {
    ans = min(ans, dist(tp, tr[x].p));
    int dl = INF, dr = INF;
    if (tr[x].ls) 
        dl = getdis(tp, tr[x].ls);
    if (tr[x].rs)
        dr = getdis(tp, tr[x].rs);
    // 爆搜，先搜最优的
    if (dl < dr) {
        if (dl < ans)
            query(tp, tr[x].ls);
        if (dr < ans)
            query(tp, tr[x].rs);
    }
    else {
        if (dr < ans)
            query(tp, tr[x].rs);
        if (dl < ans)
            query(tp, tr[x].ls);
    }
}

// query
ans = INF, query(tp, root), printf("%d\n", ans);

我tcl，只会模板题