kdTree

kd树是平衡树的多维拓展，说白了就是多维平衡树，它和普通的的区别就在于，它是按照深度决定以哪个维度作为建树划分标准的。（优化算法另当别论）
算法在注释里面已经很清楚了。

#define pow2(x) ((x)*(x))
struct kdtree{
    static const int maxn=1e5,maxkd=5;
    static int kd,idx;
    int sz[maxn<<2],spile[maxn<<2];
    struct node{
        int w[maxkd];
        bool operator<(const node&rhs)const{return w[idx]<rhs.w[idx];}
    }t[maxn<<2],in[maxn];
    priority_queue<pair<double,node> > que;

    int maxvar(int l,int r){
        int ret=0;
        double val=-1;
        for(int i=0;i<kd;i++){
            double average=0;
            for(int j=l;j<=r;j++)average+=in[j].w[i];
            average/=r-l+1;
            double variance=0;
            for(int j=l;j<=r;j++)variance+=pow2(average-in[j].w[i]);
            if(variance>val)ret=i,val=variance;
        }
        return ret;
    }

    void build(int u,int l,int r){//用前初始化kd
        if(l>r){sz[u]=0; return;}
        int mid=(l+r)>>1;
        spile[u]=idx=maxvar(l,r);
        sz[u]=r-l+1;
        nth_element(in+l,in+mid,in+r+1);
        t[u]=in[mid];
        build(u<<1|0,l,mid-1);
        build(u<<1|1,mid+1,r);
    }
    void query(int u,int m,node&q){//用前清空que
        if(sz[u]==0)return ;
        pair<double,node> tmp(0,t[u]);
        for(int i=0;i<kd;i++)tmp.first+=pow2(q.w[i]-t[u].w[i]);//dist
        int dim=spile[u];
        int closed=u<<1|(t[u].w[dim]<=q.w[dim]);//离q近的儿子
        query(closed,m,q);
        if(que.size()<m){//not full
            que.push(tmp);
            query(closed^1,m,q);//因为没满，所以要搜
        }
        else{// it is full
            if(tmp.first<que.top().first) que.pop(),que.push(tmp);//replace
            if(pow2(q.w[dim]-t[u].w[dim])<que.top().first)query(closed^1,m,q);//than maybe beter ,else it is imposable
        }
    }
}KDT;
int kdtree::idx=0,kdtree::kd=0;