洛谷 P4148:简单题 ← KD-Tree模板题

【题目来源】
https://www.luogu.com.cn/problem/P4148

【题目描述】
你有一个 N×N 的棋盘,每个格子内有一个整数,初始时的时候全部为 0,现在需要维护两种操作:
● 1 x y A → 1≤x,y≤N,A 是正整数。将格子 (x,y) 里的数字加上 A。
● 2 x1 y1 x2 y2 → 1≤x1≤x2≤N,1≤y1≤y2≤N。输出 x1,y1,x2,y2 这个矩形内的数字和
● 3 → 无终止程序

【输入格式】
输入文件第一行一个正整数 N。
接下来每行一个操作。每条命令除第一个数字之外,均要异或上一次输出的答案 last_ans,初始时 last_ans=0。

【输出格式】
对于每个 2 操作,输出一个对应的答案。

【输入样例】
4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3

【输出样例】
3
5


【说明/提示】
1≤N≤5×10^5,操作数不超过 2×10^5 个,内存限制 20MB,保证答案在 int 范围内并且解码之后数据仍合法。

【算法分析】
● KD-Tree 作为一种
二分查找树,由 Jon Louis Bentley 发明。所谓 KD-Tree,即 Multidimensional Binary Search Tree 的简称,其中的 K 表示数据空间的维度。KD-Tree 高效支持高维空间的最近邻搜索空间搜索,因此深入了解 KD-Tree 的原理以及底层实现,对机器人或无人驾驶领域的从业者来说,意义非凡。

● KD-Tree 的基本操作包括
维度划分建树插入新结点删除结点寻找第 i 维的最小值等。
其中,维度划分常用
轮转法最大方差法
(1)轮转法,即按维度交替划分。例如,若共有 K 个维度。那么,第 dep 层按 dep%K 划分,第 dep+1 层按 (dep+1)%K 划分,……。轮转法适用于所有维度的数据分布都比较均匀的情形。特别地,
针对二维平面,按 x,y 交替划分,奇数层按 x 划分,偶数层按 y 划分。
(2)最大方差法,适用于某些维度的值变化不大的情况。例如,平面上呈现为一条横线的 n 个点,x 值分布均匀,y 值相差很小,若按 y 划分没有太大意义,故选方差最大的维度 x 进行划分。方差的计算公式为:s^2=\frac{1}{n}\sum_{i=1}^{n}(x_i-\mu)^2,其中 μ 为 x 的均值。
无论采用哪种划分方法对某个维度进行划分,一般选取此维度的
中位数作为划分点,并将其作为二叉树某个子树的根。中位数常用 STL 中的 nth_element() 函数直接得到。

在数学中,给定 n 个数,当 n 为偶数时,中位数为位序 n/2+1 对应的数;当 n 为奇数时,中位数为位序 (n+1)/2 对应的数。例如:
求 (23、29、20、32、23、21、33、25) 及 (30、20、 20、 20、 10) 的中位数。
解:对 (23、29、20、32、23、21、33、25) 排序后,得 (20、21、23、23、25、29、32、33)。
由于此题中 n=8,故中位数为位序 n/2+1=8/2+1=5 对应的数25。
对 (30、20、 20、 20、 10) 排序后,得 (10、20、 20、 20、 30) 。
由于此题中 n=5,故中位数为位序 (n+1)/2=(5+1)/2=3
对应的数20。

● 利用轮转法构建 KD-Tree 的示例如下:
给定二维平面点 (x,y) 的集合 (2,3),(5,4),(9,6),(4,7),(8,1),(7,2),利用轮转法构建 KD-Tree 的过程示例如下。
(1)构建根结点:由于
奇数层按 x 划分,故将点集 (2,3),(5,4),(9,6),(4,7),(8,1),(7,2) 按 x 值排序,得 (2,3),(4,7),(5,4)(7,2)(8,1),(9,6),其中位数位序对应的结点值为 (7,2)。即将结点 (7,2) 作为根结点,(2,3),(4,7),(5,4) 将位于 (7,2) 的左子树,(8,1),(9,6) 将位于 (7,2) 的右子树。
(2)构建左子树:由于
偶数层按 y 划分,故将点集 (2,3),(4,7),(5,4) 按 y 值排序,得 (2,3)(5,4)(4,7), 其中位数位序对应的结点值为 (5,4)。即将结点 (5,4) 作为根结点,(2,3) 将位于 (5,4) 的左子树,(4,7) 将位于 (5,4) 的右子树。
(3)构建右子树:由于
偶数层按 y 划分,故将点集 (8,1),(9,6) 按 y 值排序,得 (8,1),(9,6), 其中位数位序对应的结点值为 (9,6)。即将结点 (9,6) 作为根结点,(8,1) 将位于 (9,6) 的左子树,(9,6) 右子树为空。
(4)其他结点按上述步骤逐个添加到 KD-Tree 中。

最终构建所得的 KD-Tree 如下图所示。


 

可以看出,对二维平面构建 KD-Tree 的过程,就是将二维平面逐步划分的过程。如下图所示。

维基百科给出了对三维空间构建 KD-Tree 的过程及空间划分。首先,边框为红色的竖直平面将整个空间划分为两部分。其次,此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后,此 4 个子空间又分别被边框为蓝色的竖直平面分割为两部分,变为 8 个子空间,此 8 个子空间即为叶子结点。如下图所示。


● KD-Tree 的建树插入新结点删除结点等操作,会打破 KD-Tree 的平衡。替罪羊树常用于维护 KD-Tree 的平衡。KD-Tree 当 K 等于 1 时,就是一颗替罪羊树
● 快读:
https://blog.csdn.net/hnjzsyjyj/article/details/120131534

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
const double alpha=0.75;
const int K=2;int n;
int num;
int last,root,len;
int p[K],q[K][2];
int A,D;
int h[maxn];struct KD_Tree {int le,ri;int sum,val,size;int minv[K],maxv[K],d[K];
} tr[maxn];bool cmp(const int &a,const int &b) {return tr[a].d[D]<tr[b].d[D];
}int read() { //fast readint x=0,f=1;char c=getchar();while(c<'0' || c>'9') { //!isdigit(c)if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') { //isdigit(c)x=x*10+c-'0';c=getchar();}return x*f;
}void update(int x) {int le=tr[x].le, ri=tr[x].ri;tr[x].size=tr[le].size+tr[ri].size+1;tr[x].sum=tr[le].sum+tr[ri].sum+tr[x].val;for(int i=0; i<K; i++) {if(le) {tr[x].maxv[i]=max(tr[le].maxv[i],tr[x].maxv[i]);tr[x].minv[i]=min(tr[le].minv[i],tr[x].minv[i]);}if(ri) {tr[x].maxv[i]=max(tr[ri].maxv[i],tr[x].maxv[i]);tr[x].minv[i]=min(tr[ri].minv[i],tr[x].minv[i]);}}
}void build(int &x,int le,int ri,int pos) {if(le>ri) return;int mid=(le+ri)>>1;D=pos;nth_element(h+le,h+mid+1,h+ri+1,cmp);x=h[mid];tr[x].sum=tr[x].val;for(int i=0; i<K; i++) tr[x].maxv[i]=tr[x].minv[i]=tr[x].d[i];build(tr[x].le,le,mid-1,(pos+1)%K);build(tr[x].ri,mid+1,ri,(pos+1)%K);update(x);
}void erase(int &x) {if(!x) return;h[++num]=x;erase(tr[x].le), erase(tr[x].ri);x=0;
}void rebuild(int &x,int pos) {h[num=1]=++len;tr[len].size=1;for(int i=0; i<K; i++) tr[len].d[i]=p[i];tr[len].val=tr[len].sum=A;erase(x);build(x,1,num,pos);
}void insert(int &x,int pos) {if(!x) {tr[x=++len].size=1, tr[x].val=tr[x].sum=A;for(int i=0; i<K; i++) tr[x].maxv[i]=tr[x].minv[i]=tr[x].d[i]=p[i];return;}if(p[pos]<tr[x].d[pos]) {if(tr[tr[x].le].size>tr[x].size*alpha) rebuild(x,pos);else insert(tr[x].le,(pos+1)%K);} else {if(tr[tr[x].ri].size>tr[x].size*alpha) rebuild(x,pos);else insert(tr[x].ri,(pos+1)%K);}update (x);
}bool check_range(int x) {if(!x) return 0;for(int i=0; i<K; i++) {if(q[i][0]>tr[x].minv[i] || q[i][1]<tr[x].maxv[i]) return 0;}return 1;
}bool check_point(int x) {if(!x) return 0;for(int i=0; i<K; i++) {if(tr[x].d[i]<q[i][0] || tr[x].d[i]>q[i][1]) return 0;}return 1;
}bool check(int x) {if(!x) return 0;for(int i=0; i<K; i++) {if(q[i][1]<tr[x].minv[i] || q[i][0]>tr[x].maxv[i]) return 0;}return 1;
}void query(int x) {if(check_range(x)) {last+=tr[x].sum;return;}if(check_point(x)) last+=tr[x].val;if(check(tr[x].le)) query(tr[x].le);if(check(tr[x].ri)) query(tr[x].ri);
}int main() {n=read();while(1) {int op=read();if(op==1) {for(int i=0; i<K; i++) p[i]=read()^last;A=read()^last;insert(root,0);}if(op==2) {for(int i=0; i<=1; i++) {for(int j=0; j<K; j++) q[j][i]=read()^last;}last=0;query(root);printf("%d\n",last);}if(op==3) break;}return 0;
}/*
in:
4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3out:
3
5
*/





【参考文献】
https://www.cnblogs.com/PaulShi/p/10131078.html
https://www.cnblogs.com/flyinggod/p/8727584.html
https://www.cnblogs.com/Tenshi/p/15846105.html
https://oi-wiki.org/ds/kdt/
https://www.cnblogs.com/AWCXV/p/7632254.html
https://blog.csdn.net/qq_45323960/article/details/109698448
https://www.cnblogs.com/sitiy/p/15380688.html
https://www.luogu.com.cn/problem/solution/P4148
https://www.cnblogs.com/cmy-blog/p/kdtree.html
https://zhuanlan.zhihu.com/p/112246942
https://blog.csdn.net/hnjzsyjyj/article/details/128647972


 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/321958.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux 第二十三章

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C&#xff0c;linux &#x1f525;座右铭&#xff1a;“不要等到什么都没有了…

[华为OD]C卷 机场航班调度 ,XX市机场停放了多架飞机,每架飞机都有自己的航班号100

题目&#xff1a; XX市机场停放了多架飞机&#xff0c;每架飞机都有自己的航班号CA3385, CZ6678, SC6508 等&#xff0c;航班号的前2个大写字母&#xff08;或数字&#xff09;代表航空公司的缩写&#xff0c;后面4个数字代表航班信息。 但是XX市机场只有一条起飞用跑道&am…

链舞算法谱---链表经典题剖析

前言&#xff1a;探究链表算法的奥秘&#xff0c;解锁编程新世界&#xff01; 欢迎来到我的链表算法博客&#xff0c;这将是您深入了解链表算法&#xff0c;提升编程技能的绝佳机会。链表作为数据结构的重要成员之一&#xff0c;其动态性和灵活性在实现某些功能上发挥不可替代的…

Android广播机制简介

文章目录 Android广播机制简介广播的基本概念广播的类型广播的使用场景Android广播的优缺点优点缺点 使用Android广播的一些最佳实践: Android广播机制简介 Android广播是一种轻量级的消息传递机制&#xff0c;用于应用程序之间或系统与应用程序之间进行通信。它类似于订阅-发…

缓存淘汰算法中的LRU(Least Recently Used)算法

缓存淘汰算法中&#xff0c;LRU&#xff08;Least Recently Used&#xff09;算法是一种常见的算法。它的基本思想是根据最近的访问情况来决定哪些数据被保留在缓存中&#xff0c;哪些数据被淘汰出去。 具体来说&#xff0c;当需要从缓存中淘汰数据时&#xff0c;LRU算法会选择…

OpenAI 高管:一年后,你会觉得现在的 ChatGPT 像笑话一样糟糕|TodayAI

OpenAI 的首席运营官 Brad Lightcap 表示&#xff0c;一年后&#xff0c;你会觉得现在的 ChatGPT 像笑话一样糟糕。未来的 ChatGPT 版本将会有重大升级。他还讨论了 AI 取代人类工作和对电网的压力的可能性。 虽然我们不知道 OpenAI 何时会推出 GPT-5&#xff0c;但公司高管已…

【小黑送书—第二十期】>>K邻算法:在风险传导中的创新应用与实践价值(文末送书)

01 前言 在当今工业领域&#xff0c;图思维方式与图数据技术的应用日益广泛&#xff0c;成为图数据探索、挖掘与应用的坚实基础。本文旨在分享嬴图团队在算法实践应用中的宝贵经验与深刻思考&#xff0c;不仅促进业界爱好者之间的交流&#xff0c;更期望从技术层面为企业在图数…

ADOP带你了解:长距离 PoE 交换机

您是否知道当今的企业需要的网络连接超出了传统交换机所能容纳的长度&#xff1f;这就是我们在长距离 PoE 交换机方面的专业化变得重要的地方。我们了解扩展网络覆盖范围的挑战&#xff0c;无论是在广阔的园区还是在多栋建筑之间。使用这些可靠的交换机&#xff0c;我们不仅可以…

二叉树的基础遍历2.0

1.0入口&#xff1a;二叉树的基础遍历-CSDN博客 在1.0中使用的是简单的结构体建树&#xff0c;本文注重用二维vector建树。 前序&#xff0c;中序和后序的分析1.0已给出&#xff0c;本文不做过多介绍&#xff0c;本文重点讲二叉树的层序遍历。 先奉上前中后序的代码&#xf…

算法提高之能量项链

算法提高之能量项链 核心思想&#xff1a;区间dp 通过观察发现可以将n个珠子最后的n1个数看作石子 合并石子 在l~r的范围内 找k作隔断 #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N 110,M N<<…

VMware导入ova/ovf虚拟机文件

1.文件-打开-ova文件 2.为新虚拟机起名称 3.等待导入 4.导入完成&#xff0c;可以开始使用 参考链接&#xff1a;VMware导入ova/ovf虚拟机文件

中国家装水管十大品牌排行榜:联塑、日丰、金牛、美尔固、弗锐德等品牌上榜

水管作为家居装修中至关重要的一环&#xff0c;其质量直接关系到我们日常生活的安全和舒适。面对市场上琳琅满目的家装水管品牌&#xff0c;选择一款质量可靠、性能优越的产品成为了许多家庭装修的重要课题。为了助你选购时不踩坑&#xff0c;下面就为大家介绍一下中国家装水管…

vue2 Avoided redundant navigation to current location

再次点击同一个链接会报错 每次使用 push 方法时带上两个回调函数 this.$router.push({name: item.name}, ()>{}, ()>{}) //第二、第三个参数分别为成功和失败的回调函数重写 Vue-router 原型对象上的 push 函数不行 https://blog.csdn.net/weixin_43615570/article/d…

PPPoE实验新手必备:从0到1的网络配置指南!

5月18日&#xff0c;思科华为初级网工课程&#xff0c;等你免费试听 V&#xff1a;glab-mary 今天带大家学习一下华为PPPoE实验配置 01、实验拓扑 02、实验需求 1.完成PPP封装 2.完成PPP的PAP验证 3.完成PPP的CHAP验证 4.完成R1和R2之间的PPPOE 03、实验步骤 a . PPP封…

实测幻方新出的超强AI大模型,中文能力对比GPT4.0不落下风

目前从网上的消息来看&#xff0c;DeepSeek中文综合能力&#xff08;AlignBench&#xff09;开源模型中最强&#xff0c;与GPT-4-Turbo&#xff0c;文心4.0等闭源模型在评测中处于同一梯队。 话不多说&#xff0c;我们开测&#xff01; 1.首先我们来让他直接来一段逻辑推理【并…

Leaflet在WGS84 Web墨卡托投影与WGS84经纬度投影下空间信息变形问题及修正-以圆为例

目录 前言 一、投影的相关知识 1、经纬度投影 2、Web墨卡托投影 二、经纬度投影下的空间信息展示 1、空间信息展示 2、效果展示 3、经纬度投影下的圆修正 三、Web墨卡托投影下空间信息展示 1、底图引用 2、自定义生成圆 总结 前言 在GIS的知识海洋中&#xff0c;对…

软件杯 深度学习花卉识别 - python 机器视觉 opencv

文章目录 0 前言1 项目背景2 花卉识别的基本原理3 算法实现3.1 预处理3.2 特征提取和选择3.3 分类器设计和决策3.4 卷积神经网络基本原理 4 算法实现4.1 花卉图像数据4.2 模块组成 5 项目执行结果6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &a…

Flask gevent启动报错UnicodeDecodeError

文章目录 环境代码报错Track解决思路 环境 acondana 24.1.2python 3.7.13 32bitflask 2.2.3gevent 21.8.0 代码 port 7236 logging.basicConfig(levellogging.INFO, # 控制台打印的日志级别filename./logs/app.log, # 将日志写入log_new.log文件中filemodea, # 模式&…

可视化实验三 Matplotlib库绘图及时变数据可视化

1.1 任务一 1.1.1 恢复默认配置 #绘图风格&#xff0c;恢复默认配置 plt.rcParams.update(plt.rcParamsDefault)#恢复默认配置 或者 plt.rcdefaults() 1.1.2 汉字和负号的设置 import matplotlib.pyplot as plt plt.rcParams["font.sans-serif"]"SimH…

词袋法TFIDF

Tf-idf⽂本特征提取 TF-IDF的主要思想是&#xff1a;如果某个词或短语在⼀篇⽂章中出现的概率⾼&#xff0c;并且在其他⽂章中很少出现&#xff0c;则认为此词或者短语具有很好的类别区分能⼒&#xff0c;适合⽤来分类。TF-IDF作⽤&#xff1a;⽤以评估⼀字词对于⼀个⽂件集或…