【高级数据结构】K-D Tree

$K-D Tree$ 是用来解决K维空间中数点问题强有力的数据结构，可以在 $(NlogN)$ ——$(Nsqrt{N})$ 的时间复杂度内完成查询和修改。

一、K-D Tree的做法

$K-D Tree$ 当K等于 $1$ 时，就是一颗替罪羊树树（平衡树的一种）。我们把 $K-D Tree$ 扩展到 $K$ 维空间。
$K-D Tree$ 是一颗权值树，我们对于每个树的结点用一个结构体来存

1 struct K_D_Tree{
2     int l,r,sum,val,size,Min[K],Max[K],d[K];
3 }tr[MAXN];

$l$ $r$ 分别是该结点的左孩子和右孩子

$sum$ 为以该点为根的子树区间中点权之和

$val$ 为该点所存的点的点权

$size$ 为该树为根的数中的点数

$Min[i]$ 表示在第 $i$ 维上区间的下界

$Max[i]$ 表示在第 $i$ 维上区间的上界

$d[i]$ 表示该位置表示的点的第 $i$ 维的坐标

插入操作

我们对于深度为 $i$ 的位置，我们按照第 $i%k$ 维的坐标来排序、
然后就是普通平衡树的插入即可
我们设定一个平衡因子，一般设定为 $0.6~0.9$ 之间

1 const double alpha=0.75;

当在插入是发现要插入的子树的 $size$ 比整棵树的 $size$ 的 $alpha$ 倍要大，即发现树不平衡，那么我们直接暴力重建该子树。

查询操作

直接平衡树的查询操作即可

删除操作

我们直接对要删除的点打删除标记，在插入时再删除，在查询或删除时时如果发现某颗子树的的删除标记个数大于一个定值，我们对于该子树暴力重构即可。

二、K-D Tree的几何性质

可以看上面一个以 $k$ 为 $2$ 为例的图

$K-D Tree$ 相当于每个结点对于其管辖的区间平行于坐标轴分割成一半，最后整个图被分成若干个区间，但这些区间的大小是不一致的，所以 $K-D Tree$ 是很容易被卡的。

# 模板题：

三维偏序：P4148 简单题

  1 #include<bits/stdc++.h>
  2 #define MAXN 100010
  3 using namespace std;
  4 inline int read ()
  5 {
  6     int s=0,w=1;
  7     char ch=getchar ();
  8     while (ch<'0'||ch>'9'){if (ch=='-') w=-1;ch=getchar ();}
  9     while ('0'<=ch&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar ();
 10     return s*w;
 11 }
 12 const double alpha=0.75;
 13 const int K=2;
 14 struct K_D_Tree{
 15     int l,r,sum,val,size,Min[K],Max[K],d[K];
 16 }tr[MAXN];
 17 int n,ans,root,len;
 18 int p[K],q[K][2],A;
 19 int D,num,h[MAXN];
 20 bool cmp (const int &a,const int &b)
 21 {
 22     return tr[a].d[D]<tr[b].d[D];
 23 }
 24 inline void update (int x)
 25 {
 26     int l=tr[x].l,r=tr[x].r;
 27     tr[x].size=tr[l].size+tr[r].size+1;
 28     tr[x].sum=tr[l].sum+tr[r].sum+tr[x].val;
 29     for (int i=0;i<K;i++)
 30     {
 31         if (l) tr[x].Max[i]=max (tr[l].Max[i],tr[x].Max[i]),tr[x].Min[i]=min (tr[l].Min[i],tr[x].Min[i]);
 32         if (r) tr[x].Max[i]=max (tr[r].Max[i],tr[x].Max[i]),tr[x].Min[i]=min (tr[r].Min[i],tr[x].Min[i]);
 33     }
 34 }
 35 inline void build (int &x,int l,int r,int k)
 36 {
 37     if (l>r) return;
 38     int mid=(l+r)>>1;D=k;
 39     nth_element (h+l,h+mid+1,h+r+1,cmp);
 40     x=h[mid];
 41     tr[x].sum=tr[x].val;
 42     for (int i=0;i<K;i++) tr[x].Max[i]=tr[x].Min[i]=tr[x].d[i];
 43     build (tr[x].l,l,mid-1,(k+1)%K);
 44     build (tr[x].r,mid+1,r,(k+1)%K);
 45     update (x);
 46 }
 47 inline void erase (int &x)
 48 {
 49     if (!x) return;
 50     h[++num]=x;
 51     erase (tr[x].l),erase (tr[x].r);
 52     x=0;
 53 }
 54 inline void rebuild (int &x,int k)
 55 {
 56     h[num=1]=++len;
 57     tr[len].size=1;
 58     for (int i=0;i<K;i++) tr[len].d[i]=p[i];
 59     tr[len].val=tr[len].sum=A;
 60     erase (x),build (x,1,num,k);
 61 }
 62 inline void insert (int &x,int k)
 63 {
 64     if (!x)
 65     {
 66         tr[x=++len].size=1,tr[x].val=tr[x].sum=A;
 67         for (int i=0;i<K;i++) tr[x].Max[i]=tr[x].Min[i]=tr[x].d[i]=p[i];
 68         return;
 69     }
 70     if (p[k]<tr[x].d[k])
 71     {
 72         if (tr[tr[x].l].size>tr[x].size*alpha) rebuild (x,k);
 73         else insert (tr[x].l,(k+1)%K);
 74     }
 75     else
 76     {
 77         if (tr[tr[x].r].size>tr[x].size*alpha) rebuild (x,k);
 78         else insert (tr[x].r,(k+1)%K);
 79     }
 80     update (x);
 81 }
 82 inline bool check_range (int x)
 83 {
 84     if (!x) return 0;
 85     for (int i=0;i<K;i++)
 86         if (q[i][0]>tr[x].Min[i]||q[i][1]<tr[x].Max[i]) return 0;
 87     return 1;
 88 }
 89 inline bool check_point (int x)
 90 {
 91     if (!x) return 0;
 92     for (int i=0;i<K;i++)
 93         if (tr[x].d[i]<q[i][0]||tr[x].d[i]>q[i][1]) return 0;
 94     return 1;
 95 }
 96 inline bool check (int x)
 97 {
 98     if (!x) return 0;
 99     for (int i=0;i<K;i++)
100         if (q[i][1]<tr[x].Min[i]||q[i][0]>tr[x].Max[i]) return 0;
101     return 1;
102 }
103 inline void query (int x)
104 {
105     if (check_range (x))
106     {
107         ans+=tr[x].sum;
108         return;
109     }
110     if (check_point (x)) ans+=tr[x].val;
111     if (check (tr[x].l)) query (tr[x].l);
112     if (check (tr[x].r)) query (tr[x].r);
113 }
114 int main()
115 {
116     n=read ();
117     while (1)
118     {
119         int opt=read ();
120         if (opt==1)
121         {
122             for (int i=0;i<K;i++) p[i]=read ()^ans;
123             A=read ()^ans;
124             insert (root,0);
125         }
126         if (opt==2)
127         {
128             for (int i=0;i<=1;i++)
129                 for (int j=0;j<K;j++) q[j][i]=read ()^ans;
130             ans=0;query (root);
131             printf ("%d
",ans);
132         }
133         if (opt==3) break;
134     }
135     return 0;
136 }