Kd-tree 总结
k-D Tree(KDT , k-Dimension Tree) 是一种可以 高效处理
k 维空间信息 的数据结构。在结点数
n 远大于2^k 时，应用 k-D Tree 的时间效率很好。在算法竞赛的题目中，一般有
k=2 。在本页面分析时间复杂度时，将认为k 是常数。——OI-WIKI
题目
1 x y A，将格子x,y里的数字加上A 。2 x1 y1 x2 y2，输出x_1, y_1, x_2, y_2 这个矩形内的数字和。
做法
建树
在选择的维度上选择一个中间点（中位数），将这的点作为这个子树的根，然后左右继续分开。
下一步需要换一个维度继续上面的步骤。
像这样：
首先选择了 x 轴，然后中位数是 D 点，将其作为根。
然后先到了左边，用 Y 轴比较，C 为中位数，左右两边分别是 A 和 B。
然后最后的树就是：
查询
像线段树一样分治分下去。
对于每一个点：
检查当前子树是否完全包含在查询矩形内，如果是，直接返回子树的值。
检查当前子树是否不相交于要查询的区间，如果是，直接返回
检查当前点是否在查询矩形内，如果是，继续递归，然后加上当前点的值。
插入
首先我们发现，这东西好像不太支持加点。
然后就有两种方法。
根号重构
插入的时候，存下新插入的点，当有
时间复杂度查询：
但显然不够优
二进制分组
插入时，新增一个节点的树，然后不停和其它树合并。
需要新开一个数组，记录每一个子树的根节点，每次都将会插入所有子树。
当遇到没有根节点（为空）的地方，插入当前节点，开始操作。
这时候，我们会得到一个存下了每一个子树的数组。
这就相当于拍扁（这样子树就会很少），然后新建数组。
这相当于做二进制运算，每次都会进位，每个 d[t] 都表示现在还存在的子树。
这个东西的巧妙之处在于每一个大小（
append
将子树
但注意，最后一定要将这些根节点搞成
build
直接暴力对 b 中的数重构。
就相当于合并。
注意
-
query 函数容易搞混，是
pd还是!pd很重要，这一不注意就错了。 -
cin>>xa>>ya>>xb>>yb;，输入了一定要存进去，l （查询矩形左下角），h （是右上角）。
调了
有个很神奇的问题是只犯错误
拥有详细注释的代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int last_ans=0;
struct node{
int x[2];//点的二维坐标(x,y)
int v,sum;//v是点的值，sum是子树的和
int l,r;//左右子节点
int L[2],R[2];//子树维护的矩形区域边界[L,R]
}t[1000010],l,h;//l是查询矩形左下角，h是右上角
int d[110];//不同代
int b[10000010];//用于重建的缓冲区
int cnt=0;//数量
// 更新节点p的信息
void upd(int p){
//更新当前点的和
t[p].sum=t[t[p].l].sum+t[t[p].r].sum+t[p].v;
for(int k=0;k<=1;k++){
t[p].L[k]=t[p].R[k]=t[p].x[k];
//如果有左子树，通过左子树更新边界
if(t[p].l){
t[p].L[k]=min(t[p].L[k],t[t[p].l].L[k]);
t[p].R[k]=max(t[p].R[k],t[t[p].l].R[k]);
}
//如果有右子树，通过右子树更新边界
if(t[p].r){
t[p].L[k]=min(t[p].L[k],t[t[p].r].L[k]);
t[p].R[k]=max(t[p].R[k],t[t[p].r].R[k]);
}
}
}
//每一层的比较函数
bool cmpz(int a,int b){
return t[a].x[0]<t[b].x[0];
}
bool cmpo(int a,int b){
return t[a].x[1]<t[b].x[1];
}
//构建 K-D 树
//l,r 是缓冲区 b 的左右边界，dep是当前分割的维度(0=x,1=y)
int build(int l,int r,int dep){
int mid=l+r>>1;
/*将第 k 小的数放到 k 位置上*/
if(dep==0)nth_element(b+l,b+mid,b+r+1,cmpz);
else nth_element(b+l,b+mid,b+r+1,cmpo);
// nth_element(b+l,b+mid,b+r+1,[dep](int x, int y) {
// return t[x].x[dep] < t[y].x[dep];
// });
int x=b[mid];
if(l<mid)t[x].l=build(l,mid-1,dep^1);
if(mid<r)t[x].r=build(mid+1,r,dep^1);
upd(x);
return x;
}
//将子树 p 的节点收集到缓冲区 b 中
void append(int &x){
if(!x) return;//空结点返回 0
b[++cnt]=x;
append(t[x].l);
append(t[x].r);
x=0;//最后会清空
}
/*
注意，这里容易晕，要小心。
*/
//查询矩形区域内的和
int query(int p){
if(!p)return 0;
bool pd=0;
//检查当前子树是否完全包含在查询矩形内
for(int k=0;k<=1;k++){
pd|=(!(l.x[k]<=t[p].L[k]&&t[p].R[k]<=h.x[k]));
}
// if(pd)return t[p].sum;
/*
****************
注意，这里容易晕
****************
*/
if(!pd)return t[p].sum;
//检查当前子树是否不相交
for(int k=0;k<=1;k++){
if(l.x[k]>t[p].R[k]||t[p].L[k]>h.x[k])return 0;
}
int res=0;
pd=0;
//检查当前点是否在查询矩形内
for(int k=0;k<=1;k++){
pd|=(!(l.x[k]<=t[p].x[k]&&t[p].x[k]<=h.x[k]));
}
if(!pd)res+=t[p].v;
return res+query(t[p].l)+query(t[p].r);
}
signed main(){
cin>>n;
n=0;
int o;
while(cin>>o&&o!=3){
int x,y,a,xa,ya,xb,yb;
if(o==1){
cin>>x>>y>>a;
x^=last_ans;
y^=last_ans;
a^=last_ans;
//----------
/*存入新节点*/
t[++n]={{x,y},a};
b[cnt=1]=n;
/*
这一步相当于做二进制运算，每次都会进位
每个d[t]都表示现在还存在的子树
*/
for(int t=0;;t++){
if(!d[t]){//当遇到没有根节点（为空）的地方，插入当前节点，开始操作。
/*
这个O(n)的构建不是每次插入都发生的
采用分层结构后，每个点平均只会被重建O(log n)次
*/
d[t]=build(1,cnt,0);
break;
}else{
append(d[t]);//最后会清空 d[t]
}
}
/*
这个东西的巧妙之处在于每一个大小（2 的次方）的子树都有一个，从而避免多余。
*/
}else{
cin>>xa>>ya>>xb>>yb;
xa^=last_ans;
xb^=last_ans;
ya^=last_ans;
yb^=last_ans;
//----------
last_ans=0;
/*
注意一定要存
调了30分钟
*/
l.x[0]=xa;
l.x[1]=ya;
h.x[0]=xb;
h.x[1]=yb;
for(int i=0;i<=20;i++){
last_ans+=query(d[i]);
}
cout<<last_ans<<endl;
}
}
return 0;
}
共