洛谷 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 read
    int 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
3

out:
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


 

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Shell脚本】Shell编程之条件语句

【Shell脚本】Shell编程之条件语句

目录 一.条件测试 1.test命令 1.1.test命令是内部命令 1.2.格式一 1.3.格式二 2.文件测试 2.1.常用的测试操作符 3.整数值测试 3.1.常用的测试操作符 3.2.格式一 3.3.格式二 4.字符串比较 4.1.格式一 4.2.格式二 注意&#xff1a; 5.逻辑测试 5.1.常用的测试操…
阅读更多...
机器学习 - 梯度下降算法推导

机器学习 - 梯度下降算法推导

要逐步推导多变量线性回归的梯度计算过程&#xff0c;我们首先需要明确模型和损失函数的形式&#xff0c;然后逐步求解每个参数的偏导数。这是梯度下降算法核心部分&#xff0c;因为这些偏导数将指导我们如何更新每个参数以最小化损失函数。 模型和损失函数 考虑一个多变量线…
阅读更多...
“人工智能+”推进新质生产力发展论坛暨工作室实践实训基地授牌仪式圆满结束

“人工智能+”推进新质生产力发展论坛暨工作室实践实训基地授牌仪式圆满结束

4月27日&#xff0c;由江西财经大学现代经济管理学院主办的“人工智能”推进新质生产力发展论坛暨“江财现经管泰迪数智技术”校企工作室实践实训基地授牌仪式在江西财经大学现代经济管理学院共青城校区举行&#xff0c;学院院长王金海&#xff0c;副院长丁美东&#xff0c;副院…
阅读更多...
为什么选择ATECLOUD自动化测试平台？

为什么选择ATECLOUD自动化测试平台？

在当今飞速发展的时代&#xff0c;一切都在不断进步与变革&#xff0c;电测行业也由手动测试逐步转向了自动化测试。但是随着科技的发展&#xff0c;对于产品的测试要求也越来越高&#xff0c;传统的自动化测试系统已经无法满足用户日益增长的测试需求&#xff0c;全新的ATE测试…
阅读更多...
[沫忘录]MySQL储存对象

[沫忘录]MySQL储存对象

[沫忘录]MySQL储存对象 视图 视图本质是对原表(基表)显示上的裁剪&#xff0c;可以当作表进行操作&#xff0c;其操作的结果会直接反馈到原表上&#xff0c;即对视图的操作实质上是对原表的操作。 MySQL不仅支持为基表创建视图&#xff0c;同时也支持为视图创建视图。 基本语…
阅读更多...
【C++】详解STL容器之一的 vector

【C++】详解STL容器之一的 vector

目录 概述 迭代器 数据结构 优点和缺点 接口介绍 begin end rbegin rend resize reseve insert erase 其他一些接口 模拟实现 框架 获取迭代器 深浅拷贝 赋值重载 reseve resize 拷贝构造 构造 析构 insert erase 其他 概述 vector是STL的容器之一。…
阅读更多...
用户页面触发点击事件和 js 执行点击事件的区别

用户页面触发点击事件和 js 执行点击事件的区别

文章目录 情景展示情况一&#xff1a;用户点击页面触发情况二&#xff1a;通过 js 触发点击 结果分析情况一情况二 其实这个谜底揭开之后&#xff0c;第一反应都是&#xff0c;哦~&#xff0c;非常简单&#xff0c;但是细节决定成败&#xff0c;我被这个细节毁掉了&#xff0c;…
阅读更多...
[嵌入式系统-72]：RT-Thread-组件：单元测试框架utest

[嵌入式系统-72]：RT-Thread-组件：单元测试框架utest

目录 utest 测试框架 ​编辑 测试用例定义 测试单元定义 utest 应用框图 2. utest API assert 宏 测试单元函数运行宏 测试用例导出宏 测试用例 LOG 输出接口 3. 配置使能 4. 应用范式 5. 测试用例运行要求 6. 运行测试用例 测试结果分析 7. 测试用例运行流程 …
阅读更多...
RAG 场景对Milvus Cloud向量数据库的需求

RAG 场景对Milvus Cloud向量数据库的需求

虽然向量数据库成为了检索的重要方式，但随着 RAG 应用的深入以及人们对高质量回答的需求，检索引擎依旧面临着诸多挑战。这里以一个最基础的 RAG 构建流程为例：检索器的组成包括了语料的预处理如切分、数据清洗、embedding 入库等，然后是索引的构建和管理，最后是通过 vecto…
阅读更多...
webpack从零到1 构建 vue3

webpack从零到1 构建 vue3

为什么要手写webpack 不用cli &#xff08;无的放矢&#xff09;并不是 其实是为了加深我们对webpack 的了解方便以后灵活运用webpack 的技术 初始化项目结构&#xff08;跟cli 结构保持一致&#xff09; 新建 public src 等文件夹npm init -y 创建package.json文件tsc --init…
阅读更多...
【Ubuntu20.04安装java-8-openjdk】

【Ubuntu20.04安装java-8-openjdk】

1 下载 官网下载链接&#xff1a; https://www.oracle.com/java/technologies/downloads/#java8 下载 最后一行 jdk-8u411-linux-x64.tar.gz&#xff0c;并解压&#xff1a; tar -zxvf jdk-8u411-linux-x64.tar.gz2 环境配置 1、打开~/.bashrc文件 sudo gedit ~/.bashrc2、…
阅读更多...
NGINX App Protect现已支持NGINX开源版 全方位加强现代应用安全防护

NGINX App Protect现已支持NGINX开源版 全方位加强现代应用安全防护

近日&#xff0c;F5 NGINX 发布全新升级的NGINX App Protect 5.0版本&#xff0c;将先前专属于NGINX 商业版本NGINX Plus 的现代应用安全能力拓展至NGINX开源版中&#xff0c;为增强现代应用和API安全防护提供全方位支持。此次升级后&#xff0c;适用于云端及本地部署的NGINX A…
阅读更多...
C++：位图和布隆过滤器

C++：位图和布隆过滤器

一&#xff0c;位图 1.1 位图的概念 究竟什么是位图呢&#xff1f;&#xff1f;我们用一道问题来引入 问题&#xff1a;给40亿个不重复的无符号整数&#xff0c;没排过序。给一个无符号整数&#xff0c;如何快速判断一个数是否在 这40亿个数中。【腾讯】 根据这个问题&#x…
阅读更多...
java——嵌套(二)

java——嵌套(二)

目录 一&#xff1a;方法的重写&#xff08;覆盖/覆写&#xff09; 1. 方法的重写的意义&#xff1a; 2. 重写&#xff08;overide&#xff09; 3. 案例 二&#xff1a;继承中构造方法的调用 1. 子类的构造方法会默认调用父类的构造方法&#xff1b; 2. super 关键字调用…
阅读更多...
基于MPPT最大功率跟踪和SVPWM的光伏三相并网逆变器simulink建模与仿真

基于MPPT最大功率跟踪和SVPWM的光伏三相并网逆变器simulink建模与仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 基于MPPT最大功率跟踪和SVPWM的光伏三相并网逆变器simulink建模与仿真。包括PV模块&#xff0c;MPPT模块&#xff0c;SVPWM模块&#xff0c;电网模块等。 2.系统仿真结果 1不…
阅读更多...
JavaScript异步编程——04-同源和跨域

JavaScript异步编程——04-同源和跨域

同源和跨域 同源 同源策略是浏览器的一种安全策略&#xff0c;所谓同源是指&#xff0c;域名&#xff0c;协议&#xff0c;端口完全相同。 跨域问题的解决方案 从我自己的网站访问别人网站的内容&#xff0c;就叫跨域。 出于安全性考虑&#xff0c;浏览器不允许ajax跨域获取…
阅读更多...
二总线，替代传统485总线通讯，主站设计

二总线，替代传统485总线通讯，主站设计

二总线通信设计专栏 《二总线&#xff0c;替代传统485总线通讯&#xff0c;选型及应用-CSDN博客》《二总线&#xff0c;替代传统485总线通讯&#xff0c;低成本直流载波方案实现及原理-CSDN博客》《二总线&#xff0c;替代传统485总线通讯&#xff0c;调试避坑指南之最大的电流…
阅读更多...
基于控制工程的牛鞭效应simulink建模与仿真

基于控制工程的牛鞭效应simulink建模与仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 牛鞭效应”对供应链性能和绩效产生了严重的影响。基于控制理论建立了多级线性供应链的模型&#xff0c;分别利用噪声带宽和Matlab&#xff0f;Simulink对一个可扩…
阅读更多...
【快捷部署】024_Hive（3.1.3）

【快捷部署】024_Hive（3.1.3）

&#x1f4e3;【快捷部署系列】024期信息 编号选型版本操作系统部署形式部署模式复检时间024Hive3.1.3Ubuntu 20.04tar包单机2024-05-07 一、快捷部署 #!/bin/bash ################################################################################# # 作者&#xff1a;cx…
阅读更多...
竞赛 基于深度学习的人脸性别年龄识别 - 图像识别 opencv

竞赛 基于深度学习的人脸性别年龄识别 - 图像识别 opencv

文章目录 0 前言1 课题描述2 实现效果3 算法实现原理3.1 数据集3.2 深度学习识别算法3.3 特征提取主干网络3.4 总体实现流程 4 具体实现4.1 预训练数据格式4.2 部分实现代码 5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 毕业设计…
阅读更多...
最新文章

Copyright @ 2022~2023