\(kd-tree\) 是一种比较毒瘤的数据结构，不是很常考，会的人也不是很多。但是NOI考过，省选也考过，有时候也可以干一点暴力的事。
一般带修，可插入，允许强制在线（只是麻烦一点），然后查询就稀奇古怪了，比如给个矩形，问矩形里有几个点（据说二维的可以树套树，可是我不会），或者给每个点一个权值，问矩形里点权和，再或者把矩形改成某种奇怪的解析式，比如圆、椭圆什么的。
关于 \(kd-tree\) ，我觉得它和线段树很像，都可以打标记，然后还可以扩展到k维，这就是为什么叫\(kd-tree\)
\(kd-tree\) 是采用循环分割的方法建树的。什么叫循环分割？每次按照某一维为关键字排序，取出中位数，然后以这个节点为根，把[l,mid-1],[mid+1,r]作为左右子树，进行分割。光说不太好理解，上代码。
int cmp_D;
bool cmp(const node &a,const node &b){return a.d[cmp_d]<b.d[cmp_d];}
int build(int l,int r,int D){
int mid=l+r>>1;cmp_d=D;
nth_element(t+l,t+mid,t+r+1,cmp);
t[mid].mx[0]=t[mid].mn[0]=t[mid].d[0];
t[mid].mx[1]=t[mid].mn[1]=t[mid].d[1];
if(l!=mid)t[mid].ls=build(l,mid-1,D%k+1);
if(r!=mid)t[mid].rs=build(mid+1,r,D%k+1);
up(mid);return mid;
}关于那个 \(nth\_lement\) 据说是均摊 \(O(n)\) 把中位数放到mid的位置，其余数据不保证有序（和sort很像）
然后就是 \(kd-tree\) 的优化了（它也是因为这个才那么快）包围盒
包围盒，就是这个节点底下的子树的最小、最大横坐标、纵坐标。可以在pushup的时候记录。还是看代码。
void pushup(int p) {
tr[p].sz=1,tr[p].sum=tr[p].tp.val;
tr[p].mn[0]=tr[p].mx[0]=tr[p].tp.d[0];
tr[p].mn[1]=tr[p].mx[1]=tr[p].tp.d[1];
if(tr[p].ls) {
tr[p].mn[0]=min(tr[p].mn[0],tr[tr[p].ls].mn[0]);
tr[p].mn[1]=min(tr[p].mn[1],tr[tr[p].ls].mn[1]);
tr[p].mx[0]=max(tr[p].mx[0],tr[tr[p].ls].mx[0]);
tr[p].mx[1]=max(tr[p].mx[1],tr[tr[p].ls].mx[1]);
tr[p].sz+=tr[tr[p].ls].sz,tr[p].sum+=tr[tr[p].ls].sum;
}
if(tr[p].rs) {
tr[p].mn[0]=min(tr[p].mn[0],tr[tr[p].rs].mn[0]);
tr[p].mn[1]=min(tr[p].mn[1],tr[tr[p].rs].mn[1]);
tr[p].mx[0]=max(tr[p].mx[0],tr[tr[p].rs].mx[0]);
tr[p].mx[1]=max(tr[p].mx[1],tr[tr[p].rs].mx[1]);
tr[p].sz+=tr[tr[p].rs].sz,tr[p].sum+=tr[tr[p].rs].sum;
}
}这种都可以灵活记录，主要看题目，但是mn，mx一般都会记下来。
然后说说为什么就快起来了。
有了包围盒，在查询的时候，比如上面要查询每个矩形内有几个点，就可以判断这个点的包围盒是否在矩形外，如果是，那么直接舍掉，因为不可能对答案产生贡献。否则，就像线段树一样进去分左右子树查询。
而且在数据随机的情况下，很可能一次少一颗子树，所以均摊 \(O(n\log n)\) ，而且求正交平面的时候严格 \(O(n\log n)\) （就是线段树）
例题1：
描述
有一列元素，每一个元素有三个属性:标号、标识符、数值。这些元素按照标号从1~n排列，标识符也是1~n的一个排列，初始时数值为0。当然我们可以把每个元素看成一个多维数字，那么这列元素就是一个数列。
现在请你维护这个数列，使其能支持以下两种操作：
1.将标号为l~r的所有元素的数值先乘上x，再加上y；
2.将标识符为l~r的所有元素的数值先乘上x，再加上y。
当然你还得回答某些询问：
1.标号为l~r的所有元素的数值的和；
2.标识符为l~r的所有元素的数值的和。
输入
第一行有两个正整数n、m，分别表示数列长度和操作与询问个数的总和。
第二行有n个正整数，表示每个元素的标识符，保证这n个数是1~n的一个排列。
接下来m行，每行的第一个数字为op。若op为0，则表示要进行第一个操作，接下去四个数字表示l,r,x,y;若op为1，则表示要进行第二个操作，接下去四个数字表示l,r,x,y;若op为2，则表示要回答第一个询问，接下去两个数字表示l,r;若op为3，则表示要回答第二个询问，接下去两个数字表示l,r。
输出
包含若干行，每行表示一个询问的答案。由于答案可能很大，只要请你输出答案对536870912取模后的值即可。
可以把 \((i,{p_i})\) 看作2维平面上的点，标识符是横着的矩形，区间是竖着的矩形，然后查询区间和，打个懒惰标记。cnt记录区间内有几个点，val是当前点的权值，sum是当前的区间和，这样懒标就可以下传了。其实这题和线段树很像
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50005;
const int mod=536870912;
struct node{
int d[2],mn[2],mx[2],ls,rs;
int cnt,sum,val;
int pl,ti;
}t[N];
int n,m,ans,rt,tpl,tti;
int op,l,r,x,y,dir,cmp_d;
void up(int u){
t[u].cnt=1;
if(t[u].ls){
t[u].cnt+=t[t[u].ls].cnt;
t[u].mx[0]=t[u].mx[0]>t[t[u].ls].mx[0]?t[u].mx[0]:t[t[u].ls].mx[0];
t[u].mx[1]=t[u].mx[1]>t[t[u].ls].mx[1]?t[u].mx[1]:t[t[u].ls].mx[1];
t[u].mn[0]=t[u].mn[0]<t[t[u].ls].mn[0]?t[u].mn[0]:t[t[u].ls].mn[0];
t[u].mn[1]=t[u].mn[1]<t[t[u].ls].mn[1]?t[u].mn[1]:t[t[u].ls].mn[1];
}
if(t[u].rs){
t[u].cnt+=t[t[u].rs].cnt;
t[u].mx[0]=t[u].mx[0]>t[t[u].rs].mx[0]?t[u].mx[0]:t[t[u].rs].mx[0];
t[u].mx[1]=t[u].mx[1]>t[t[u].rs].mx[1]?t[u].mx[1]:t[t[u].rs].mx[1];
t[u].mn[0]=t[u].mn[0]<t[t[u].rs].mn[0]?t[u].mn[0]:t[t[u].rs].mn[0];
t[u].mn[1]=t[u].mn[1]<t[t[u].rs].mn[1]?t[u].mn[1]:t[t[u].rs].mn[1];
}
}
bool cmp(const node &a,const node &b){return a.d[cmp_d]<b.d[cmp_d];}
int build(int l,int r,int D){
int mid=l+r>>1;cmp_d=D;
nth_element(t+l,t+mid,t+r+1,cmp);
t[mid].mx[0]=t[mid].mn[0]=t[mid].d[0];
t[mid].mx[1]=t[mid].mn[1]=t[mid].d[1];
if(l!=mid)t[mid].ls=build(l,mid-1,D^1);
if(r!=mid)t[mid].rs=build(mid+1,r,D^1);
up(mid);return mid;
}
void f(int x,int ti,int pl){
t[x].val=(t[x].val*ti+pl)%mod;
t[x].sum=(t[x].sum*ti+pl*t[x].cnt)%mod;
t[x].ti=(t[x].ti*ti)%mod;
t[x].pl=(t[x].pl*ti+pl)%mod;
}
void down(int u){
if(t[u].pl==1&&t[u].ti==0)return;
if(t[u].ls)f(t[u].ls,t[u].ti,t[u].pl);
if(t[u].rs)f(t[u].rs,t[u].ti,t[u].pl);
t[u].ti=1;t[u].pl=0;
}
void update(int u){
if(t[u].mx[dir]<l||t[u].mn[dir]>r)return;
if(l<=t[u].mn[dir]&&t[u].mx[dir]<=r){f(u,tti,tpl);return;}
down(u);
if(t[u].d[dir]>=l&&t[u].d[dir]<=r)t[u].val=(t[u].val*x+y)%mod;
if(t[u].ls)update(t[u].ls);
if(t[u].rs)update(t[u].rs);
t[u].sum=(t[u].val+t[t[u].ls].sum+t[t[u].rs].sum)%mod;
}
void ask(int u)
{
if(t[u].mx[dir]<l||t[u].mn[dir]>r)return;
if(l<=t[u].mn[dir]&&t[u].mx[dir]<=r){ans=(ans+t[u].sum)%mod;return;}
down(u);
if(l<=t[u].d[dir]&&t[u].d[dir]<=r)ans=(ans+t[u].val)%mod;
if(t[u].ls)ask(t[u].ls);
if(t[u].rs)ask(t[u].rs);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld",&t[i].d[1]),t[i].d[0]=i;
rt=build(1,n,0);
while(m--){
scanf("%lld",&op);
if(op==0){
scanf("%lld%lld%lld%lld",&l,&r,&x,&y);
dir=0;tpl=y%mod;tti=x%mod;update(rt);
}
if(op==1){
scanf("%lld%lld%lld%lld",&l,&r,&x,&y);
dir=1;tpl=y%mod;tti=x%mod;update(rt);
}
if(op==2){
scanf("%lld%lld",&l,&r);
dir=0;ans=0;ask(rt);
printf("%lld\n",ans);
}
if(op==3){
scanf("%lld%lld",&l,&r);
dir=1;ans=0;ask(rt);
printf("%lld\n",ans);
}
}
return 0;
} 然后就是上面说到的强制在线的问题了。插入当然可以暴力把点塞进去，但是多了就会比较麻烦：因为数据可以不断地卡 \(kd-tree\) ，卡成一条链，时间复杂度就爆炸了。
对于那些不强制在线的题，可以直接把所有点先插进去，对于目前在树上和不在树上的点打标记，插入后更新标记就好了。
然而强制在线的话……
就要用到替罪羊树的思想拍平重构，所以会多一只 \(log\) 就是这么来的（据说可以treap重构，但是我不会qwq）
扔道重构树的例题：P4148 简单题
这题与上题相比不用记录那么多东西，就是强制在线比较恶心，要重构。
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,lastans,root;
struct point {
int d[2],val;
} a[N];
struct node {
int sum,ls,rs,mx[2],mn[2],sz;
point tp;
} tr[N];
int tot,top,rub[N];
int min(const int &a,const int &b) {
return a<b?a:b;
}
int max(const int &a,const int &b) {
return a>b?a:b;
}
int newnode() {
return top?rub[top--]:++tot;
}
void pushup(int p) {
tr[p].sz=1,tr[p].sum=tr[p].tp.val;
tr[p].mn[0]=tr[p].mx[0]=tr[p].tp.d[0];
tr[p].mn[1]=tr[p].mx[1]=tr[p].tp.d[1];
if(tr[p].ls) {
tr[p].mn[0]=min(tr[p].mn[0],tr[tr[p].ls].mn[0]);
tr[p].mn[1]=min(tr[p].mn[1],tr[tr[p].ls].mn[1]);
tr[p].mx[0]=max(tr[p].mx[0],tr[tr[p].ls].mx[0]);
tr[p].mx[1]=max(tr[p].mx[1],tr[tr[p].ls].mx[1]);
tr[p].sz+=tr[tr[p].ls].sz,tr[p].sum+=tr[tr[p].ls].sum;
}
if(tr[p].rs) {
tr[p].mn[0]=min(tr[p].mn[0],tr[tr[p].rs].mn[0]);
tr[p].mn[1]=min(tr[p].mn[1],tr[tr[p].rs].mn[1]);
tr[p].mx[0]=max(tr[p].mx[0],tr[tr[p].rs].mx[0]);
tr[p].mx[1]=max(tr[p].mx[1],tr[tr[p].rs].mx[1]);
tr[p].sz+=tr[tr[p].rs].sz,tr[p].sum+=tr[tr[p].rs].sum;
}
}
int cmp_D;
bool cmp(const point &a,const point &b) {
return a.d[cmp_D]<b.d[cmp_D];
}
int build(int l,int r,int D) {
if(l>r)return 0;
int mid=(l+r)>>1,p=newnode();
cmp_D=D;
nth_element(a+l,a+mid+1,a+r+1,cmp);
tr[p].tp=a[mid];
tr[p].ls=build(l,mid-1,D^1);
tr[p].rs=build(mid+1,r,D^1);
pushup(p);
return p;
}
void beat(int p,int num) {//拍平
if(tr[p].ls)beat(tr[p].ls,num);
a[tr[tr[p].ls].sz+num+1]=tr[p].tp,rub[++top]=p;
if(tr[p].rs)beat(tr[p].rs,tr[tr[p].ls].sz+num+1);
}
void check(int &p,int D) {//重构
if(tr[p].sz*0.75<tr[tr[p].ls].sz||tr[p].sz*0.75<tr[tr[p].rs].sz)
beat(p,0),p=build(1,tr[p].sz,D);
}
void ins(int &p,point o,int D) {
if(!p) {
p=newnode();
tr[p].ls=tr[p].rs=0;
tr[p].tp=o;
pushup(p);
return;
}
if(o.d[D]<=tr[p].tp.d[D])ins(tr[p].ls,o,D^1);
else ins(tr[p].rs,o,D^1);
pushup(p);
check(p,D);
}
bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2) {
return x1<=X1&&X2<=x2&&y1<=Y1&&Y2<=y2;
}
bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2) {
return x1>X2||x2<X1||y1>Y2||y2<Y1;
}
int query(int p,int x1,int y1,int x2,int y2) {
if(!p)return 0;
int res=0;
if(in(x1,y1,x2,y2,tr[p].mn[0],tr[p].mn[1],tr[p].mx[0],tr[p].mx[1]))return tr[p].sum;
if(out(x1,y1,x2,y2,tr[p].mn[0],tr[p].mn[1],tr[p].mx[0],tr[p].mx[1]))return 0;
if(in(x1,y1,x2,y2,tr[p].tp.d[0],tr[p].tp.d[1],tr[p].tp.d[0],tr[p].tp.d[1]))res+=tr[p].tp.val;
res+=query(tr[p].ls,x1,y1,x2,y2)+query(tr[p].rs,x1,y1,x2,y2);
return res;
}
int main() {
scanf("%d",&n);
int opt,X1,Y1,X2,Y2,A;
while("fyy AK IOI") {//据说在这里字符串与"1"的效果是一样的。
scanf("%d",&opt);
if(opt==3)return 0;
if(opt==1) {
scanf("%d%d%d",&X1,&X2,&A);
X1^=lastans,X2^=lastans,A^=lastans;
ins(root,point {X1,X2,A},0);
}
if(opt==2) {
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
X1^=lastans,Y1^=lastans,X2^=lastans,Y2^=lastans;
printf("%d\n",lastans=query(root,X1,Y1,X2,Y2));
}
}
}此文将会持续更新，因为博主最近在练习 \(kd-tree\) ，更新完毕的时候将会发现这句话不见了qwq。