K-D Tree 學(xué)習(xí)筆記

最近看了一下k-NN然后它說(shuō)如果特征空間維數(shù)比較低的時(shí)候用K-D Tree來(lái)求k近鄰比較快所以就來(lái)補(bǔ)一下學(xué)OI時(shí)沒(méi)學(xué)的K-D Tree假裝寫一個(gè)學(xué)習(xí)筆記吧。

是什么？

是一個(gè)平衡二叉樹

k=1的時(shí)候就是一只BST

k>1的話，每一層換一維來(lái)分割

就是用許多垂直坐標(biāo)軸的超平面將一個(gè)k維空間分割

每個(gè)節(jié)點(diǎn)保存了一個(gè)點(diǎn)，它所代表的超平面就是經(jīng)過(guò)這個(gè)點(diǎn)垂直于某個(gè)坐標(biāo)軸一個(gè)超平面

每個(gè)子樹代表了一個(gè)區(qū)域（代碼實(shí)現(xiàn)中是包含子樹中所有點(diǎn)的最小超矩形，實(shí)際上應(yīng)該是劃分后的那個(gè)超矩形

怎么做？

建樹

我沒(méi)有任何建樹，下一個(gè)

復(fù)雜度\(O(kn\log n)\)，一個(gè)分治...

插入

直接插入就行了，注意一路update

挺不科學(xué)的插入的話會(huì)破壞建樹時(shí)的平衡性

所以要加入重構(gòu)好麻煩不想寫

查詢

有點(diǎn)詭異的啟發(fā)式搜索

有一個(gè)估算一個(gè)點(diǎn)到一個(gè)超矩形的最大/最小距離的操作

對(duì)于最近鄰來(lái)說(shuō)，先搜左右兒子中距離近的，并且只搜估算最近距離小于當(dāng)前ans的

k近鄰的話，用個(gè)大根堆，一直保持堆中有k個(gè)的元素

遠(yuǎn)的話換成遠(yuǎn)就行了QwQ

聽說(shuō)隨機(jī)數(shù)據(jù)復(fù)雜度\(O(\log n)\)到\(O(n\sqrt{n})\) ，不會(huì)證不會(huì)證

代碼實(shí)現(xiàn)

因?yàn)樵缇屯艘哿怂晕乙矝](méi)有做很多題來(lái)練習(xí)各種鬼畜用法的必要了扔模板就跑

bzoj2648 帶插入最近鄰

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e6+5, inf = 1e9;
#define lc t[x].ch[0]
#define rc t[x].ch[1]
#define max0(x) max(x, 0)

int n, m;
int curD = 0;
struct meow {
    int d[2];
    meow() {}
    meow(int x, int y){d[0]=x; d[1]=y;}
    bool operator < (const meow &r) const {
        return d[curD] < r.d[curD];
    }
    int calDist(meow &a) {
        return abs(d[0] - a.d[0]) + abs(d[1] - a.d[1]);
    }
};
meow a[N];
struct node {
    int ch[2], x[2], y[2];
    meow p;
    void update(node &a) {
        x[0] = min(x[0], a.x[0]); x[1] = max(x[1], a.x[1]);
        y[0] = min(y[0], a.y[0]); y[1] = max(y[1], a.y[1]);
    }
    void set(meow &a) {
        p = a;
        x[0] = x[1] = a.d[0];
        y[0] = y[1] = a.d[1];
    }
    int evaDist(meow &a) {
        int xx = a.d[0], yy = a.d[1];
        return max0(x[0] - xx) + max0(xx - x[1]) + max0(y[0] - yy) + max0(yy - y[1]);
    }
} t[N];
int root;
int build(int l, int r, int d) {
    curD = d;
    int x = (l+r)>>1;
    nth_element(a+l, a+x, a+r+1);
    t[x].set(a[x]);
    if(l < x) lc = build(l, x-1, d^1), t[x].update(t[lc]);
    if(x < r) rc = build(x+1, r, d^1), t[x].update(t[rc]);
    return x;
}
void insert(meow q) {
    t[++n].set(q);
    for(int x=root, D=0; x; D^=1) {
        t[x].update(t[n]);
        int &nxt = t[x].ch[q.d[D] >= t[x].p.d[D]];
        if(nxt == 0) {
            nxt = n;
            break;
        }
        else x = nxt;
    }
}

int ans;
void query(int x, meow q) {
    int nowDist = t[x].p.calDist(q), d[2];
    d[0] = lc ? t[lc].evaDist(q) : inf;
    d[1] = rc ? t[rc].evaDist(q) : inf;
    int wh = d[1] <= d[0];
    ans = min(ans, nowDist);
    if(d[wh] < ans) query(t[x].ch[wh], q);
    wh ^= 1;
    if(d[wh] < ans) query(t[x].ch[wh], q);
}

int main() {
    cin >> n >> m;
    int c, x, y;
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &x, &y);
        a[i] = meow(x, y);
    }
    root = build(1, n, 0);
    for(int i=1; i<=m; i++) {
        scanf("%d %d %d", &c, &x, &y);
        if(c == 1) insert(meow(x, y));
        else {
            ans = inf;
            query(root, meow(x, y));
            printf("%d\n", ans);
        }
    }
}

bzoj4520 k遠(yuǎn)點(diǎn)對(duì)

每個(gè)點(diǎn)求一次k遠(yuǎn)點(diǎn)

值得注意的是會(huì)TLE所以整體用一個(gè)大根堆才行

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll inf = 1e18;
#define lc t[x].ch[0]
#define rc t[x].ch[1]
#define max0(x) max(x, 0)

inline ll sqr(ll x) {return x*x;}

int n, K;
int curD = 0;
struct meow {
    ll d[2];
    meow() {}
    meow(ll x, ll y){d[0]=x; d[1]=y;}
    bool operator < (const meow &r) const {
        //if(d[curD] == r.d[curD]) return d[curD^1] < r.d[curD^1];
        return d[curD] < r.d[curD];
    }
    ll calDist(meow &a) {
        //return abs(d[0] - a.d[0]) + abs(d[1] - a.d[1]);
        return sqr(d[0] - a.d[0]) + sqr(d[1] - a.d[1]);
    }
};
meow a[N];
struct node {
    int ch[2], x[2], y[2];
    meow p;
    void update(node &a) {
        x[0] = min(x[0], a.x[0]);
        x[1] = max(x[1], a.x[1]);
        y[0] = min(y[0], a.y[0]);
        y[1] = max(y[1], a.y[1]);
    }
    void set(meow &a) {
        p = a;
        x[0] = x[1] = a.d[0];
        y[0] = y[1] = a.d[1];
    }
    ll evaMaxDist(meow &a) {
        ll xx = a.d[0], yy = a.d[1];
        return max(sqr(x[0]-xx), sqr(x[1]-xx)) + max(sqr(y[0]-yy), sqr(y[1]-yy));
    }
} t[N];
int root;
int build(int l, int r, int d) {
    curD = d;
    int x = (l+r)>>1;
    nth_element(a+l, a+x, a+r+1);
    t[x].set(a[x]);
    if(l < x) {
        lc = build(l, x-1, d^1);
        t[x].update(t[lc]);
    }
    if(x < r) {
        rc = build(x+1, r, d^1);
        t[x].update(t[rc]);
    }
    return x;
}

priority_queue<ll, vector<ll>, greater<ll> > ans;
void query(int x, meow q) {
    ll nowDist = t[x].p.calDist(q), d[2];
    d[0] = lc ? t[lc].evaMaxDist(q) : -inf;
    d[1] = rc ? t[rc].evaMaxDist(q) : -inf;
    int wh = d[1] >= d[0];
    if(nowDist > ans.top()) ans.pop(), ans.push(nowDist);
    if(d[wh] > ans.top()) query(t[x].ch[wh], q);
    wh ^= 1;
    if(d[wh] > ans.top()) query(t[x].ch[wh], q);
}

int main() {
    cin >> n >> K; K <<= 1;
    int x, y;
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &x, &y);
        a[i] = meow(x, y);
    }
    root = build(1, n, 0);
    for(int j=1; j<=K; j++) ans.push(-inf);
    for(int i=1; i<=n; i++) {
        query(root, a[i]);
    } 
    cout << ans.top() << endl;
}