K-D Tree初探

Author Avatar
Sakits 7月 26, 2018

简介

  简称KDT,全称K-Dimension Tree。
  KDT是一棵平衡二叉树,是一个用于维护矩阵信息的数据结构。

构成

  KDT中的一个节点,储存了一个KK维度空间域和一个KK维的点坐标。
  KDT上的一个节点,主要由以下三部分组成:
    d[k]d[k]:这个节点储存的点的kk维坐标。
    l[k]/r[k]l[k]/r[k]:这个节点储存/管辖的KK维空间域,形象地说这个点是这个区域的“首领”。
    lt/rtlt/rt:这个节点的左右儿子。
  KDT是一棵平衡二叉树,所以它的每一个节点都代表着KK维空间域上的实际存在的一个点,是有实际意义的。

建树

  一般题目都是二维平面上的,希望OI生涯中不要遇到出KK维的毒瘤出题人(flag)…
  std::nth_element()是一个stl函数,能在期望O(n)O(n)的时间内查询并定位长度为nn的数组中第kk小的元素,并将比它小的数丢到它前面,比它大的丢到它后面(前面后面都无序),具体实现就是个快排。
  构造KDT的规则如下:
    11.随着树的深度增加,循环的选取坐标轴,作为分割超平面的法向量。对于3-D Tree来说,根节点选取xx轴,根节点的孩子选取yy轴,根节点的孙子选取zz轴,根节点的曾孙子选取xx轴,这样循环下去。
    22.每次均为当前点集中,选中某一维坐标的中位数的点作为切分点,切分点作为父节点,左右两侧为划分的作为左右两子树。
  这样建树显然是二叉平衡的,所以建树的复杂度为O(Knlogn)O(Knlogn)

inline void newnode(int x)
{
    tree[x].sum+=P.w; tree[x].w+=P.w;
    tree[x].ls=tree[x].rs=0;
    for(int i=0;i<2;i++)
    tree[x].d[i]=tree[x].l[i]=tree[x].r[i]=P.d[i];
}
   
inline void up(int x)
{
    tree[x].sum=tree[x].w;
    tree[x].sum+=tree[lt].sum; tree[x].sum+=tree[rt].sum;
    for(int i=0;i<2;i++)
    {
        if(lt) mins(tree[x].l[i], tree[lt].l[i]); maxs(tree[x].r[i], tree[lt].r[i]);
        if(rt) mins(tree[x].l[i], tree[rt].l[i]); maxs(tree[x].r[i], tree[rt].r[i]);
    }
}
   
void build(int &x, int l, int r, int ty)
{
    x=++tott; int mid=(l+r)>>1;
    now=ty; nth_element(p+l, p+mid, p+r+1);
    P=p[mid]; tree[x].sum=tree[x].w=0; newnode(x); 
    if(l<mid) build(lt, l, mid-1, ty^1);
    if(mid<r) build(rt, mid+1, r, ty^1);
    up(x);
}

插入

  如果会插入老点,加一句特判要覆盖信息还是添加信息。

inline void up(int x)
{
    tr[x].sum=tr[x].w+tr[lt].sum+tr[rt].sum;
    tr[x].size=tr[lt].size+tr[rt].size+1;
    for(int i=0;i<2;i++)
    {
        if(lt) mins(tr[x].l[i], tr[lt].l[i]), maxs(tr[x].r[i], tr[lt].r[i]);
        if(rt) mins(tr[x].l[i], tr[rt].l[i]), maxs(tr[x].r[i], tr[rt].r[i]);
    }
}
 
void insert(int &x, int ty)
{
    if(!x) {x=++tott; newnode(x); now=x; return;}
    if(tr[x].d[0]==P.d[0] && tr[x].d[1]==P.d[1]) 
    {
        tr[x].sum+=P.w; tr[x].w+=P.w; now=0;
        return; 
    }
    tmp[++dep]=x;
    if(P.d[ty]<=tr[x].d[ty]) insert(lt, ty^1);
    else insert(rt, ty^1);
    up(x);
}
 
inline bool cmp(int a, int b){return tr[a].d[cmpd]<tr[b].d[cmpd];}
 
void build(int &x, int l, int r, int ty)
{
    int mid=(l+r)>>1; cmpd=ty; 
    nth_element(np+l, np+mid, np+r+1, cmp); x=np[mid];
    for(int i=0;i<2;i++) tr[x].l[i]=tr[x].r[i]=tr[x].d[i];
    if(l<mid) build(lt, l, mid-1, ty^1); else lt=0;
    if(mid<r) build(rt, mid+1, r, ty^1); else rt=0;
    up(x);
}
 
void dfs(int x){if(x) np[++cnt]=x, dfs(lt), dfs(rt);}
 
inline void work(int &x)
{
    dep=0; insert(x, 0); if(!now) return;
    while(max(tr[tr[now].ls].size, tr[tr[now].rs].size)<A*tr[now].size) now=tmp[--dep];
    if(!now) return; 
    cnt=0; dfs(now);
    if(now==x) build(x, 1, cnt, 0);
    else
    {
        int fa=tmp[--dep];
        int k; build(k, 1, cnt, dep&1);
        if(tr[fa].ls==now) tr[fa].ls=k; else tr[fa].rs=k;
    }
}

  KDT的插入是无法维护平衡的,所以我们必须像替罪羊树一样估计某棵子树不平衡时重构整棵子树。

查询

  每个点都需要维护当前点的信息和所管辖的区域的总信息。
  如果查询区域覆盖了某个点管辖的区域,直接返回所管辖区域总信息。
  否则如果查询区域覆盖了当前点,给答案加上当前点的信息,并查询左右子树。

inline bool cross(int x)
{
    if(!x) return 0;
    if(q.x>tr[x].r[0]) return 0;
    if(q.y>tr[x].r[1]) return 0;
    if(q.x2<tr[x].l[0]) return 0;
    if(q.y2<tr[x].l[1]) return 0;
    return 1;
}
 
int query(int x)
{
    if(q.x<=tr[x].l[0] && q.y<=tr[x].l[1] && tr[x].r[0]<=q.x2 && tr[x].r[1]<=q.y2) return tr[x].sum;
    int ans=0;
    if(q.x<=tr[x].d[0] && q.y<=tr[x].d[1] && tr[x].d[0]<=q.x2 && tr[x].d[1]<=q.y2) ans+=tr[x].w;
    if(cross(lt)) ans+=query(lt);
    if(cross(rt)) ans+=query(rt);
    return ans;
}

板子(单点加矩阵查+替罪羊树重构)

https://www.lydsy.com/JudgeOnline/showsource.php?id=2861759

例题

例题1 bzoj2648:SJY摆棋子

  kdt的启发式操作题…查询到一个点时先用这个点更新答案,然后用估价函数判断先走左子树还是先走右子树,如果答案比某子树的估价还要小的话,就没必要走那个子树了。
  估价函数为查询点到当前点管辖区域的最短距离,如果在管辖区域内则为00,这个最短距离显然是\leq答案的,所以正确性显然。
  最坏复杂度据说是O(nn)O(n\sqrt{n}),不知道怎么证明,毕竟是启发式操作…

例题2 bzoj4605:崂山白花蛇草水