K-D Tree

细节

KDT和树套树并非等价，树套树一般是时间\(O(n\log^2n)\)，空间\(O(n\log n)\)的，KDT是时间\(O(n\log n+n\sqrt n)\)（修改+查询），空间\(O(n)\)

子树递归时，值域越界判断不要像线段树一样写\(L<=mid,R>mid\)，而是转到儿子去写，不然会报错，因为一层只判一个维度，另一个维度可能越界，所以要两个维度都判，因此转到儿子两个维度一起判最方便(AC WA)

重构KDT时，全部树都重构和重构最高的子树一样快（亲测

代码

int n,q,ver[M],a[M],b[M],cx[M],cy[M],ntot;
bool cmp1(int x,int y) {return cx[x]<cx[y];}
bool cmp2(int x,int y) {return cy[x]<cy[y];}
struct KDT {
	int s[M],son[M][2],rtot; double alpha=0.6;
	void Pushup(int x) {s[x]=s[son[x][0]]+s[son[x][1]]+1;}
	int Build(int l,int r,int dep) {
		if(l>r) return 0;
		int mid=(l+r)>>1;
		nth_element(b+l,b+mid,b+r+1,dep&1?cmp1:cmp2);
		son[b[mid]][0]=Build(l,mid-1,dep+1);
		son[b[mid]][1]=Build(mid+1,r,dep+1);
		Pushup(b[mid]);
		return b[mid];
	}
	void GetTree(int x) {
		if(!x) return;
		b[++rtot]=x;
		GetTree(son[x][0]);
		GetTree(son[x][1]);
	}
	void Insert(int &x,int dep,int k) {
		if(!x) {x=k,s[k]=1; return;}
		Insert(son[x][dep&1?cx[k]>cx[x]:cy[k]>cy[x]],dep+1,k);
		Pushup(x);
		if(1.0*s[son[x][0]]/s[x]>alpha||1.0*s[son[x][1]]/s[x]>alpha) rtot=0,GetTree(x),x=Build(1,rtot,dep);
	}
	int Query(int x,int l1,int r1,int l2,int r2,int L1,int R1,int L2,int R2,int dep) {
		if(!x||l1>R1||r1<L1||l2>R2||r2<L2) return 0;
		if(l1>=L1&&r1<=R1&&l2>=L2&&r2<=R2) return s[x];
		int ret=0; ret+=(cx[x]>=L1&&cx[x]<=R1&&cy[x]>=L2&&cy[x]<=R2);
		if(dep&1) {
			ret+=Query(son[x][0],l1,cx[x],l2,r2,L1,R1,L2,R2,dep+1);
			ret+=Query(son[x][1],cx[x],r1,l2,r2,L1,R1,L2,R2,dep+1);
		}
		else {
			ret+=Query(son[x][0],l1,r1,l2,cy[x],L1,R1,L2,R2,dep+1);
			ret+=Query(son[x][1],l1,r1,cy[x],r2,L1,R1,L2,R2,dep+1);
		}
		return ret;
	}
}tr;