首页 > 其他 > 详细

KD-tree 学习小记

时间:2019-07-20 00:46:49      阅读:146      评论:0      收藏:0      [点我收藏+]

\(NOI\) 时不会,感觉很亏。于是学了一上午,写了一晚上。
感觉这东西就是个复杂度玄学的高级暴力 (大雾

KD-tree 基本信息

\(D\) 就是 \(Dimension\) ,维度的意思。 \(KD-tree\) 就是用来解决多维点的问题。
它可以说是一棵平衡树,但建树时用来比较的东西很奇特。
查询几乎与线段树类似,但更暴力一些。每次查询的复杂度为 \(O(n^{\frac{k-1}{k}})\)

最常见的时平面上点的问题,也就是 \(2D-tree\)
有时它的功能可被树套树或 \(CDQ\) 分治实现,它的时间复杂度不如那两者优。
但是它写起来容易,而且在限制空间或在线时是很好的选择。


基本操作

  • 建树 \(build\)

大体思路与平衡树类似,但特别的地方是权值的比较——各个维度轮流作为关键字来比较。
所以在建树的过程中需要一个变量来记当前以哪一维为关键字。
之后我们要找一个根节点,然后比根节点小的扔到左子,大的扔到右子,分别递归
那为保证树的平衡,根节点就是中位数咯
\(STL\) 有一个高级函数 \(nth_element()\) 可以在 \(O(n)\) 实现找第 \(k\) 小的点,并将比它小或大的点分居在它两侧。
借助它就能在 \(O(Knlogn)\) 完成建树了。

  • 插入 \(insert\)

与平衡树的插入类似,就是按照比较权值的方法,小的往左子走,大的往右子走。

  • 拍扁重构 \(check+pia+build\)

为了保证树的平衡,类似替罪羊树,在插入后判断树是否失衡(即左子或右子的 \(size\) 过大)
如果失衡,就暴力重构这个子树。
具体地,就是先遍历一遍,把子树中所有点都拿出来。然后对这个子树 \(build\)
注意空间的回收利用,可以用一个栈保存删掉的点的地址。

  • 查询 \(query\)

与线段树类似,但非常非常暴力。
若整个区间满足条件,就用维护好的有关整个区间的东西;不满足,就分别询问当前点及两个子树。
需要用到剪枝、乱搞等技巧。

首先,为了查询方便,每个节点要记录子树的范围,即子树中各维度的 \(mn\)\(mx\)
然后可以设置估值函数。
根据估值函数的大小我们可以决定进不进某个子树、先进哪个子树等等……


模板

洛谷 \(P4169\) \([Violet]天使玩偶/ SJY 摆棋子\)
求最小曼哈顿距离。

#include<cstdio>
#include<iostream>
#include<algorithm>

#define INF 10000000

using namespace std;

int read(){
    int x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x; 
}

const int N = 300005;

int n,D;
struct data { 
    int d[2];
    data() { d[0]=d[1]=0; }
    data(int x,int y) { d[0]=x; d[1]=y; }
    bool operator < (const data &b) const{ return d[D]<b.d[D]; } 
}a[N],b[N*2];
int tot;

struct tree{
    tree *ch[2];
    int mx[2],mn[2],d[2],sz;
}pool[N*2],*st[N*2],*root;
int cnt,top;
tree *New() { return top?st[--top]:&pool[++cnt]; }
int mn(tree *p,int i) { return p ? p->mn[i] : INF ; }
int mx(tree *p,int i) { return p ? p->mx[i] : -INF ; }
int sz(tree *p) { return p ? p->sz : 0 ; }
void update(tree *p){
    for(int i=0;i<2;i++){
        p->mx[i]=max(p->d[i],max(mx(p->ch[0],i),mx(p->ch[1],i)));
        p->mn[i]=min(p->d[i],min(mn(p->ch[0],i),mn(p->ch[1],i)));
    }
    p->sz=1+sz(p->ch[0])+sz(p->ch[1]);
}
tree *build(data A[],int l,int r,int de){
    if(l>r) return NULL;
    tree *p=New();
    int mid=(l+r)>>1;
    D=de; nth_element(A+l,A+mid,A+r);
    p->d[0]=A[mid].d[0]; p->d[1]=A[mid].d[1];
    p->ch[0]=build(A,l,mid-1,de^1);
    p->ch[1]=build(A,mid+1,r,de^1);
    update(p);
    return p; //别忘了返回值!
}
void pia(tree *p){
    if(p->ch[0]) pia(p->ch[0]);
    st[top++]=p;
    b[++tot].d[0]=p->d[0]; b[tot].d[1]=p->d[1];
    if(p->ch[1]) pia(p->ch[1]);
}
tree *check(tree *p,int de){
    if(1.0*sz(p->ch[0])<=0.75*p->sz && 1.0*sz(p->ch[1])<=0.75*p->sz) return p;
    tot=0; pia(p);
    return build(b,1,tot,de);
}
void insert(tree *p,tree *nd,int de){
    int f=nd->d[de]>p->d[de];
    if(!p->ch[f]) p->ch[f]=nd;
    else insert(p->ch[f],nd,de^1);
    p->ch[f]=check(p->ch[f],de^1);
    update(p);
}
int getdis(tree *p,data x){
    if(!p) return INF;
    int ret=0;
    for(int i=0;i<2;i++) ret+=max(0,p->mn[i]-x.d[i])+max(0,x.d[i]-p->mx[i]);
    return ret;
}
int ans;
void query(tree *p,data x){
    if(!p) return;
    ans=min(ans,abs(p->d[0]-x.d[0])+abs(p->d[1]-x.d[1]));
    int d0=getdis(p->ch[0],x),d1=getdis(p->ch[1],x);
    if(d0>=ans && d1>=ans) return;
    if(d0<d1){
        query(p->ch[0],x);
        if(d1<ans) query(p->ch[1],x);
    }
    else{
        query(p->ch[1],x);
        if(d0<ans) query(p->ch[0],x);
    }
}

int main()
{
    int m,t,x,y;
    n=read(); m=read();
    for(int i=1;i<=n;i++){
        a[i].d[0]=read();
        a[i].d[1]=read();
    }
    
    root=build(a,1,n,0);
    while(m--){
        t=read(); x=read(); y=read();
        if(t==1){
            tree *nd=New();
            nd->sz=1; 
            nd->mn[0]=nd->mx[0]=nd->d[0]=x;
            nd->mn[1]=nd->mx[1]=nd->d[1]=y;
            insert(root,nd,0); root=check(root,0);
        }
        else{<C
            ans=INF;
            data c(x,y);
            query(root,c);
            printf("%d\n",ans); 
        }
    }
    
    return 0;
} 

洛谷 \(P4475 巧克力王国\)

没有新插入的点,所以不需要拍扁重构。
查询时临界点就是4个端点:
若它们中最大的 \(<C\) ,则全部满足;若最小的 \(\geq C\) ,则全不满足。
其实这也等价于判断4个点中有几个满足 \(<C\) ,若4个,则全部满足;若0个,则全不满足。

我嫌指针版常数过大,换了数组版,写着或看着都好清爽呀~
注意 \(long\) \(long\)

#include<cstdio>
#include<iostream>
#include<algorithm>

#define INF 1000000005
#define ll long long

using namespace std;

int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch) && ch!='-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}
ll lread(){
    int f=1;
    ll x=0;
    char ch=getchar();
    while(!isdigit(ch) && ch!='-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}

const int N = 500005;

int D;
struct data{
    int d[2],val,id;
    data() { d[0]=d[1]=val=id=0; }
    data(int x,int y,int c,int i) { d[0]=x; d[1]=y; val=c; id=i; }
    bool operator < (const data &b) const{ return d[D]<b.d[D]; }
}a[N];

int ch[N][2],mx[N][2],mn[N][2],d[N][2],root;
ll val[N],sum[N];
void update(int x){
    for(int i=0;i<2;i++){
        mx[x][i]=max(d[x][i],max(mx[ch[x][0]][i],mx[ch[x][1]][i]));
        mn[x][i]=min(d[x][i],min(mn[ch[x][0]][i],mn[ch[x][1]][i]));
    }
    sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]];
}
int build(int l,int r,int ty){
    if(l>r) return 0;
    int mid=(l+r)>>1;
    D=ty; nth_element(a+l,a+mid,a+r+1);
    int x=a[mid].id;
    ch[x][0]=build(l,mid-1,ty^1);
    ch[x][1]=build(mid+1,r,ty^1);
    update(x);
    return x;
}
ll ans,A,B,C;
ll cal(int x,int y) { return A*x+B*y; }
void ask(int x){
    if(!x) return;
    int t=0;
    if(cal(mn[x][0],mn[x][1])<C) t++;
    if(cal(mn[x][0],mx[x][1])<C) t++;
    if(cal(mx[x][0],mn[x][1])<C) t++;
    if(cal(mx[x][0],mx[x][1])<C) t++;
    if(t==0) return;
    if(t==4) { ans+=sum[x]; return; }
    if(cal(d[x][0],d[x][1])<C) ans+=val[x];
    ask(ch[x][0]); ask(ch[x][1]);
}

int main()
{
    int n,m;
    n=read(); m=read();
    for(int i=1;i<=n;i++){
        d[i][0]=read(); d[i][1]=read(); val[i]=lread();
        a[i]=data(d[i][0],d[i][1],val[i],i);
    }
    for(int i=0;i<=n;i++) {
        ch[i][0]=ch[i][1]=0;
        mx[i][0]=mx[i][1]=-INF; mn[i][0]=mn[i][1]=INF;
        sum[i]=0;
    }
    root=build(1,n,0);
    
    while(m--){
        A=lread(); B=lread(); C=lread();
        ans=0;
        ask(root);
        printf("%lld\n",ans);
    }
    
    return 0;
} 

KD-tree 学习小记

原文:https://www.cnblogs.com/lindalee/p/11215968.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!