当前位置： ag凯发k8国际 > 编程资源 > 编程问答 >内容正文

编程问答

kd树小结 -ag凯发k8国际

发布时间：2023/12/18 编程问答 15 豆豆

ag凯发k8国际收集整理的这篇文章主要介绍了 kd树小结小编觉得挺不错的,现在分享给大家,帮大家做个参考.

很久之前我就想过怎么快速在二维平面上查找一个区域的信息，思考许久无果，只能想到几种优秀一点的暴力。

kd树就是干上面那件事的。

别的不多说，赶紧把自己的理解写下来，免得凉了。

kd树的组成

以维护k维空间(x,y,……)内的kd树为例，主要由一下三部分组成：

p[k]，代表树上这个结点所储存的点(在题目中给出的/你自己加上的点集中的一个点)。

ch[2]，表示它的子结点(没错，kd树是一棵二叉树)

mi[k]与mx[k]，mi/mx[i]代表kd树这个结点统辖的所有点的第i-1范围。比如说mi[1]=2,mx[1]=4，就代表这棵树统辖的点的y坐标都在[2,4]内。

不看mi和mx，长得就和splay/trie树一样，一个p维护当前节点，一个ch[2]记录左右儿子。

不看p[k]，长得就和线段树一样，有左右儿子和区间信息。

没错，kd树功能如线段树，结点维护区域信息；形态如splay/trie树，每个结点有实际的值和意义。

kd树的构建

一般题目都是二维平面。下面就以二维平面kd树的构建为例。

读入把点存进结构体数组a中，坐标分别为a[x].p[i]。

inline void build(int &x,int l,int r,int type){x=(l r)>>1;now=type;nth_element(a l,a x,a r 1,cmp);nd=a[x];newnode(x);if(l0],l,x-1,type^1);else ch[x][0]=0;if(x1],x 1,r,type^1);else ch[x][1]=0;pushup(x); }build(kd.root,1,n,0);

非常优美……对type、now作用不明的同学请继续阅读……你要现在就明白就奇怪了

系统函数nth_element(a l,a x,a r 1)，头文件algorithm，需定义＜或cmp函数。

作用：把排序后第x大的放到第x位，比它小的放进左边，比它大的放进右边(两边无序)。

注意区间开闭：左闭右开，中间也是闭合的。

复杂度：平均，期望是o(n)？可以接受。

下面给出cmp、newnode、pushup代码。

struct node{int p[2],mi[2],mx[2];}a[n]; inline bool cmp(const node &a,const node &b){return a.p[now]<b.p[now];} inline void min(int &x,int y){x=xx:y;} inline void max(int &x,int y){x=x>y?x:y;} inline void pushup(int x){int ls=ch[x][0],rs=ch[x][1];if(ls){min(t[x].mi[0],t[ls].mi[0]);max(t[x].mx[0],t[ls].mx[0]);min(t[x].mi[1],t[ls].mi[1]);max(t[x].mx[1],t[ls].mx[1]);}if(rs){min(t[x].mi[0],t[rs].mi[0]);max(t[x].mx[0],t[rs].mx[0]);min(t[x].mi[1],t[rs].mi[1]);max(t[x].mx[1],t[rs].mx[1]);} }inline void newnode(int x){t[x].p[0]=t[x].mi[0]=t[x].mx[0]=nd.p[0];t[x].p[1]=t[x].mi[1]=t[x].mx[1]=nd.p[1]; }

不要问我为什么辣么长，为了减常冲榜，把循环展开了……

聪明的读者已经发现kd树的构建巧妙之处。它不是纯粹按照x维，或者某一维排序，而是先按x维，再按y维，再按z维，再……最后又回到x维……

这样分割的区域更加整齐划一更加均匀紧缩，不像上面的按照某一维划分，到最后变成一条条长条，kd树划分到底的图案还是很好看的。

这样分割有什么好处呢？等你真正领悟了kd树的精髓之后你就会发现……嘿嘿嘿……

(就是为了把这个暴力数据结构剪枝剪更多跑更快)

kd树的操作

1.往kd树上插点

插点可以分为插新点和插老点。如果有老点，特判一句，把信息覆盖即可。

inline void insert(int &x,int type){if(!x){x= cnt,newnode(cnt);return;}if(nd.p[0]==t[x].p[0] && nd.p[1]==t[x].p[1]){……(自行维护);return;}if(nd.p[type]0],type^1);else insert(ch[x][1],type^1);pushup(x); }

依然非常的美妙……等等有什么不对？

我们能估计出一棵刚建好的kd树深度是o(log)的。

但你这么随便乱插……有道题叫hnoi2017 spaly 插入不旋转的单旋spaly见过？t成苟。

这都不是问题！知不知道有一种数据结构叫做替罪羊树哇？

知道替罪羊树怎么保证复杂度的吗？

重构！大力重构！自信重构！不爽就重构！

为了省事大概每插入10000次就重构一次好了……

if(kd.cnt==sz){for(int i=1;i<=sz; i)a[i]=kd.t[i];kd.rebuild(kd.root,1,sz,0);sz =10000; }

2.在kd树上查询

如果是单点(给定点)查询：
- 太简单啦！把插入改改就阔以辣！
如果是查询距离一个点(x',y')最近的点(曼哈顿距离，|x-x'| |y-y'|)：
- 首先我们看暴力的剪枝：按某一维排序，如果该维的差过大就不管了。
- 而令我们期待的kd树呢？呃不好意思，它也是这么做的……
- 我们维护过两个叫做mi[]和mx[]的东西吧……这个时候就是它派上用场了。
- 具体还请看代码吧： //查询的点(x',y')储存在nd中。 //这里的l,r就是mi,mx的意思。 inline int dis(node p,int x,int ans=0){for(int i=0;i<2; i)ans =max(0,t[x].l[i]-p.p[i]) max(0,p.p[i]-t[x].r[i]);return ans; }inline void query(int x){ans=min(ans,abs(t[x].p[0]-nd.p[0]) abs(t[x].p[1]-nd.p[1]));int dl=ch[x][0]?dis(nd,ch[x][0]):inf;int dr=ch[x][1]?dis(nd,ch[x][1]):inf;if(dl<dr){if(dl0]);if(dr1]);}else{if(dr1]);if(dl0]);} }
- dis():如果当前点在这个区间内就是0，否则就是最极的点到它的距离。
- 聪明绝顶的你已经发现了……这tm就是个暴力。
- 其实这个数据结构就是一个暴力……
- 当暴力有了时间复杂度证明……还叫暴力么？读书人的事，能叫偷么？
- 这么暴力有几个好处：不用枚举所有点；剪枝有效及时。
- 复杂度有保障，大概在o(√n)级别下，主要看数据。
如果是区间查询，以区间查询点权和为例(之前就有维护好)：
- inline bool in(int l,int r,int xl,int xr){return l<=xl && xr<=r;} inline bool out(int l,int r,int xl,int xr){return xrxl;}inline int query(int x,int x1,int y1,int x2,int y2){int ans=0;if(!x)return ans;if(in(x1,x2,t[x].mi[0],t[x].mx[0]))if(in(y1,y2,t[x].mi[1],t[x].mx[1]))return t[x].sum;if(out(x1,x2,t[x].mi[0],t[x].mx[0]))return 0;if(out(y1,y2,t[x].mi[1],t[x].mx[1]))return 0;if(in(x1,x2,t[x].p[0],t[x].p[0]))if(in(y1,y2,t[x].p[1],t[x].p[1]))ans =t[x].val;return ans query(ch[x][0],x1,y1,x2,y2) query(ch[x][1],x1,y1,x2,y2); }
- 别看代码长又看起来复杂，写起来跟线段树似的，还是一样的暴力搞。

kd树的基本姿势大概就是这个样子……好写不好写错，基本上都是个板子。

附上学长的一(三)句话，从各方面进行了深度总结：

“能不写最好还是不要写吧，轻松被卡→_→，也许可以出奇制胜？如果要写，重新构树是个不错的选择。发现大数据跑不过，多半是剪枝挂了。”

还是给个链接……mashirosky大爷。

upd:以当前坐标差最大的来做type应该比轮换type更优秀……

例题有"sjy摆棋子"、"简单题"等，在此就不做赘述了。

比较有意思的应用就是【bzoj3489】 a simple rmq problem，正如上面所言，kd树解决传统数据结构题出奇制胜。

附上"bzoj4066简单题"代码一份，操作是单点修改矩形求和在线。

#include #include #include #include #include #include #include #include #include #define ll long long int #define dob double #define file "bzoj_4066" //#define file "简单题" using namespace std;const int n = 200010; int n,lst,now,sz=10000;inline int gi(){int x=0,res=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}while(ch<='9'&&ch>='0')x=x*10 ch-48,ch=getchar();return x*res; }inline void min(int &x,int y){x=xx:y;} inline void max(int &x,int y){x=x>y?x:y;} struct node{int p[2],mi[2],mx[2],val,sum;}a[n]; inline bool cmp(const node &a,const node &b){return a.p[now]<b.p[now];} struct kd_tree{int ch[n][2],root,cnt;node t[n],nd;inline void pushup(int x){int ls=ch[x][0],rs=ch[x][1];if(ls){min(t[x].mi[0],t[ls].mi[0]);max(t[x].mx[0],t[ls].mx[0]);min(t[x].mi[1],t[ls].mi[1]);max(t[x].mx[1],t[ls].mx[1]);}if(rs){min(t[x].mi[0],t[rs].mi[0]);max(t[x].mx[0],t[rs].mx[0]);min(t[x].mi[1],t[rs].mi[1]);max(t[x].mx[1],t[rs].mx[1]);}t[x].sum=t[x].val;if(ls)t[x].sum =t[ls].sum;if(rs)t[x].sum =t[rs].sum;}inline void newnode(int x){t[x].p[0]=t[x].mi[0]=t[x].mx[0]=nd.p[0];t[x].p[1]=t[x].mi[1]=t[x].mx[1]=nd.p[1];t[x].sum=t[x].val=nd.val;}inline void insert(int &x,int type){if(!x){x= cnt,newnode(cnt);return;}if(nd.p[0]==t[x].p[0] && nd.p[1]==t[x].p[1]){t[x].val =nd.val;t[x].sum =nd.val;return;}if(nd.p[type]0],type^1);else insert(ch[x][1],type^1);pushup(x);}inline void rebuild(int &x,int l,int r,int type){x=(l r)>>1;now=type;nth_element(a l,a x,a r 1,cmp);nd=a[x];newnode(x);if(l0],l,x-1,type^1);else ch[x][0]=0;if(x1],x 1,r,type^1);else ch[x][1]=0;pushup(x);}inline bool in(int l,int r,int xl,int xr){return l<=xl && xr<=r;}inline bool out(int l,int r,int xl,int xr){return xrxl;}inline int query(int x,int x1,int y1,int x2,int y2){int ans=0;if(!x)return ans;if(in(x1,x2,t[x].mi[0],t[x].mx[0]))if(in(y1,y2,t[x].mi[1],t[x].mx[1]))return t[x].sum;if(out(x1,x2,t[x].mi[0],t[x].mx[0]))return 0;if(out(y1,y2,t[x].mi[1],t[x].mx[1]))return 0;if(in(x1,x2,t[x].p[0],t[x].p[0]))if(in(y1,y2,t[x].p[1],t[x].p[1]))ans =t[x].val;return ans query(ch[x][0],x1,y1,x2,y2) query(ch[x][1],x1,y1,x2,y2);}}kd;int main() {freopen(file".in","r",stdin);freopen(file".out","w",stdout);n=gi();while(1){int type=gi();if(type==3)break;int x1=gi()^lst,y1=gi()^lst;if(type==1){int a=gi()^lst;kd.nd.p[0]=x1;kd.nd.p[1]=y1;kd.nd.sum=kd.nd.val=a;kd.insert(kd.root,0);if(kd.cnt==sz){for(int i=1;i<=sz; i)a[i]=kd.t[i];kd.rebuild(kd.root,1,sz,0);sz =10000;}}if(type==2){int x2=gi()^lst,y2=gi()^lst;lst=kd.query(kd.root,x1,y1,x2,y2);printf("%d\n",lst);}}fclose(stdin);fclose(stdout);return 0; } 简单题

转载于:https://www.cnblogs.com/fenghaoran/p/8176236.html

总结

以上是ag凯发k8国际为你收集整理的kd树小结的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。