(K-D Tree)是一种可以高效处理(k)维空间信息的数据结构
(K-D Tree)具有二叉搜索树的形态，二叉搜索树上的每个结点都对应(k)维空间内的一个点。其每个子树中的点都在一个(k)维的超长方体内，这个超长方体内的所有点也都在这个子树中
同时用(ma)和(mi)来记录划分出的子空间的边界
建树的过程是不断划分(k)维空间的过程
在(K-D Tree)上，第(i)层中的节点的关键字为节点所对应的空间中的点的第(i mod k)维坐标
以二维举例
第一层在(x)轴上选取中位数作为根，第二层在(y)轴上选取中位数作为根，第三层在(x)轴上选取中位数作为根，以此类推
建树的时间复杂度为(O(n log n))
在(K-D Tree)上查询时，若直接遍历整棵树，时间复杂度为(O(n))，所以需进行剪枝，使复杂度降到(O(sqrt n))
K远点对：查询二维平面上欧氏距离下的第(k)远点对
(code:)
struct KD_tree
{
ll d[2];
int mi[2],ma[2],ls,rs,id;
}t[maxn],dat[maxn];
bool cmp(const KD_tree &a,const KD_tree &b)
{
return a.d[type]<b.d[type];
}
void pushup(int cur)
{
int ls=t[cur].ls,rs=t[cur].rs;
for(int i=0;i<=1;++i)
{
t[cur].ma[i]=t[cur].mi[i]=t[cur].d[i];
if(ls)
{
t[cur].ma[i]=max(t[cur].ma[i],t[ls].ma[i]);
t[cur].mi[i]=min(t[cur].mi[i],t[ls].mi[i]);
}
if(rs)
{
t[cur].ma[i]=max(t[cur].ma[i],t[rs].ma[i]);
t[cur].mi[i]=min(t[cur].mi[i],t[rs].mi[i]);
}
}
}
void build(int l,int r,int k,int &cur)
{
cur=++tot,type=k;
int mid=(l+r)>>1;
nth_element(dat+l+1,dat+mid+1,dat+r+1,cmp);
t[cur]=dat[mid];
if(l<mid) build(l,mid-1,k^1,t[cur].ls);
if(r>mid) build(mid+1,r,k^1,t[cur].rs);
pushup(cur);
}
ll calc(ll x)
{
return x*x;
}
ll dis(int cur,ll x,ll y)
{
return calc(t[cur].d[0]-x)+calc(t[cur].d[1]-y);
}
ll dist(int cur,ll x,ll y)
{
return max(calc(t[cur].ma[0]-x),calc(t[cur].mi[0]-x))+max(calc(t[cur].ma[1]-y),calc(t[cur].mi[1]-y));
}
void query(int cur,ll x,ll y)
{
ll d,dl,dr;
int ls=t[cur].ls,rs=t[cur].rs;
d=dis(cur,x,y);
if(d>q.top()) q.pop(),q.push(d);
if(ls) dl=dist(ls,x,y);
else dl=-inf;
if(rs) dr=dist(rs,x,y);
else dr=-inf;
if(dl>q.top()) query(ls,x,y);
if(dr>q.top()) query(rs,x,y);
}
......
for(int i=1;i<=2*k;++i) q.push(0);
for(int i=1;i<=n;++i)
query(root,dat[i].d[0],dat[i].d[1]);
巧克力王国：查询二维平面上满足(ax+by < c)（每次询问给出(a b c)）的点的权值和
(code:)
struct KD_tree
{
int d[2],mi[2],ma[2],ls,rs,id;
ll val,sum;
}t[maxn],dat[maxn];
bool cmp(const KD_tree &a,const KD_tree &b)
{
return a.d[type]<b.d[type];
}
void pushup(int cur)
{
int ls=t[cur].ls,rs=t[cur].rs;
for(int i=0;i<=1;++i)
{
t[cur].ma[i]=t[cur].mi[i]=t[cur].d[i];
if(ls)
{
t[cur].ma[i]=max(t[cur].ma[i],t[ls].ma[i]);
t[cur].mi[i]=min(t[cur].mi[i],t[ls].mi[i]);
}
if(rs)
{
t[cur].ma[i]=max(t[cur].ma[i],t[rs].ma[i]);
t[cur].mi[i]=min(t[cur].mi[i],t[rs].mi[i]);
}
}
t[cur].sum=t[ls].sum+t[rs].sum+t[cur].val;
}
void build(int l,int r,int k,int &cur)
{
cur=++tot,type=k;
int mid=(l+r)>>1;
nth_element(dat+l+1,dat+mid+1,dat+r+1,cmp);
t[cur]=dat[mid];
if(l<mid) build(l,mid-1,k^1,t[cur].ls);
if(r>mid) build(mid+1,r,k^1,t[cur].rs);
pushup(cur);
}
bool check(ll x,ll y)
{
return a*x+b*y<c;
}
ll query(int cur)
{
ll ans=0;
int ls=t[cur].ls,rs=t[cur].rs,cnt=0;
cnt+=check(t[cur].ma[0],t[cur].ma[1]);
cnt+=check(t[cur].ma[0],t[cur].mi[1]);
cnt+=check(t[cur].mi[0],t[cur].mi[1]);
cnt+=check(t[cur].mi[0],t[cur].ma[1]);
if(cnt==4) return t[cur].sum;
if(!cnt) return 0;
if(check(t[cur].d[0],t[cur].d[1])) ans+=t[cur].val;
if(ls) ans+=query(ls);
if(rs) ans+=query(rs);
return ans;
}
简单题：支持插入点和查询二维平面上矩形内所有点的权值和，强制在线，用(K-D Tree)实现，当不平衡时，像替罪羊树一样重构
(code:)
struct KD_tree
{
int d[2],mi[2],ma[2],ls,rs,val,sum,siz;
}t[maxn],dat[maxn],p;
bool cmp(const KD_tree &a,const KD_tree &b)
{
return a.d[type]<b.d[type];
}
int add()
{
if(top) return st[top--];
return ++tot;
}
void pushup(int cur)
{
int ls=t[cur].ls,rs=t[cur].rs;
for(int i=0;i<=1;++i)
{
t[cur].ma[i]=t[cur].mi[i]=t[cur].d[i];
if(ls)
{
t[cur].ma[i]=max(t[cur].ma[i],t[ls].ma[i]);
t[cur].mi[i]=min(t[cur].mi[i],t[ls].mi[i]);
}
if(rs)
{
t[cur].ma[i]=max(t[cur].ma[i],t[rs].ma[i]);
t[cur].mi[i]=min(t[cur].mi[i],t[rs].mi[i]);
}
}
t[cur].sum=t[ls].sum+t[rs].sum+t[cur].val;
t[cur].siz=t[ls].siz+t[rs].siz+1;
}
void build(int l,int r,int k,int &cur)
{
cur=add(),type=k;
int mid=(l+r)>>1;
nth_element(dat+l+1,dat+mid+1,dat+r+1,cmp);
t[cur]=dat[mid];
t[cur].ls=t[cur].rs=0;
if(l<mid) build(l,mid-1,k^1,t[cur].ls);
if(r>mid) build(mid+1,r,k^1,t[cur].rs);
pushup(cur);
}
void del(int cur)
{
if(!cur) return;
dat[++now]=t[cur];
st[++top]=cur;
del(t[cur].ls),del(t[cur].rs);
}
void check(int &cur,int k)
{
int ls=t[cur].ls,rs=t[cur].rs;
if(t[cur].siz*alpha<max(t[ls].siz,t[rs].siz))
now=0,del(cur),build(1,t[cur].siz,k,cur);
}
void insert(KD_tree p,int k,int &cur)
{
if(!cur)
{
cur=add();
t[cur]=p;
t[cur].ls=t[cur].rs=0;
pushup(cur);
return;
}
if(p.d[k]<=t[cur].d[k]) insert(p,k^1,t[cur].ls);
else insert(p,k^1,t[cur].rs);
pushup(cur);
check(cur,k);
}
bool check_p(KD_tree p)
{
return p.d[0]<=bx&&p.d[0]>=ax&&p.d[1]<=by&&p.d[1]>=ay;
}
bool check_in(KD_tree p)
{
return p.mi[0]>=ax&&p.ma[0]<=bx&&p.mi[1]>=ay&&p.ma[1]<=by;
}
bool check_out(KD_tree p)
{
return p.mi[0]>bx||p.ma[0]<ax||p.mi[1]>by||p.ma[1]<ay;
}
int query(int cur)
{
int ls=t[cur].ls,rs=t[cur].rs,val=t[cur].val,sum=t[cur].sum,ans=0;
if(check_in(t[cur])) return sum;
if(check_out(t[cur])) return 0;
if(check_p(t[cur])) ans+=val;
if(ls) ans+=query(ls);
if(rs) ans+=query(rs);
return ans;
}